These swords were likely central in the battle of the Fall of Gondolin, in the first age. Gondolin was the largest and most powerful of the Noldor elves' cities, and its fall was possibly one of the most important victories for the orcs during the first age. Which in turn would make it one of the greatest victories in the history of orcs. Surely the orcs would have legends just like the elves, so the names of their foes and their weapons would be passed down through the ages.
Glamdring belonged to Turgon, the King of Gondolin - who is actually Elrond's great-grandfather - so it would be reputed by that alone.
But also, the Fall of Gondolin was truly an epic battle, with numerous dragons and balrogs facing various Noldor elven heroes. Mere orcs must have been complete cannon fodder in this monumental battle, meaning that the swords could have gotten their reputation and their orcish epithets there.
Another possibility, and this is speculation, the swords could have been forged for the Nírnaeth Arnoediad (Battle of the Unnumbered Tears), a battle during a war that happened earlier, when the elves were on the offensive. Turgon had time to prepare for this war in advance and knew they would be facing orcs. It would be possible that Glamdring and Orcrist where forged for this war and made their reputation there.
We don't know who wielded Orcrist, but Turgon could potentially have wielded Glamdring during Nírnaeth Arnoediad. The forces of Gondolin turned the tide in the battle, so it seems fitting that these swords were prominent there. Whereas during the Fall of Gondolin, Turgon died.
The city of Gondolin was built in a secret location and nobody left it or entered it, until Turgon marched his armies out in the open during Nírnaeth Arnoediad. Therefore, the swords could only have earned their reputation during these great wars and not elsewhere, due to the secrecy around Gondolin.
It wouldn't have been possible to earn a reputation over time, like for example Beleg's/Turin's black sword Anglachel, which earned its reputation over time in many smaller border skirmishes, rather than in big battles. If Glamdring/Orcrist were ever used by rangers to defend Gondolin against scouting orcs, no orc obviously lived to tell the tale, or the location of Gondolin would have been revealed.
So the orc legends must originate from either or both of the mentioned battles.
Stepping out of the lore, among Tolkien's earliest works was the story of the Fall of Gondolin, a stand-alone story for a long time. It was only woven in with the rest of the Tolkien stories much later. When Tolkien wrote The Hobbit, he borrowed bits and pieces from the Fall of Gondolin, likely without the intention to ever bring the stories together, at that point.
He later does the same when writing Lord of the Rings, making the Noldor hero Glorfindel appear in the book, although he actually died back in the first age, fighting a balrog during the Fall of Gondolin. Tolkien admitted himself that this was an inconsistency in his lore, and came up with some 'patch' about Glorfindel getting resurrected.
So Glamdring and Orchrist (and Sting) are kind of anachronisms, much like Glorfindel.