"i know you your (insert generic name here) The destroyer of elfs"
I know this is going to sound petty, but I couldn't understand this first time round. Took a couple of read-throughs.
Try:
"I know you. You're (insert generic name here), the Destroyer of elves."
The biggest error was the "your/you're" one. The lack of punctuation, incorrect (usually lacking) uppercasing and the whole "elfs/elves" thing[1] mattered very little, really. But "your" (belonging to you) and "you're" (contraction of "you are") led me down a false semantic trail when parsing it all.
Right, enough of that. What I had since decided to point out was along the following lines.
"Urist De Chipping-Sodbury" might indeed be from CS, or just have become famous there. So it occurs to me that the game has multiple choices from which randomness might still be useful.
Urist of <Homeland> (...Robin of Loxley)
Urist of <Fameland> (...Robin of Sherwood)
Urist the <SignificantlyKilledRace> Killer (...Jack the Giant Killer)
Urist <SignificantKilledEntity>-Bane (...may not end up named, so could be "Wolf-Bane")
Urist, Saviour of <PlaceFromWhichQuestsWereAskedAndLaterAnswered>
Urist the <WeaponType> (...Mack the Knife)
<Hair/Beard/etcColour> Urist (...Red Ken, although that's political colour)
<Size/Anti-size> Urist (...think "Little John" for the latter option)
Urist of the <OrganisationalAllegiance/Alliance/Acquaintance> (...having once killed some pesky bandit at the behest of the randomly generated entity group given the random title The Wandering Veils, now Urist is known (to the one who recognises him) as "Urist of The Wandering Veils"... regardless of whether that actually makes much sense outside of context
)
Lord Urist (...or any other title, probably outside of the current entity encoded ranges such as Baron or King, unless there's good reason for it, but "Swordmaster Urist" or "Sureshot Urist" might be useful additions terms based upon the reason for fame, as well as whatever non-Noble, but 'noble', titles could be dredged up to agree with the particular level of fame/infamy being expressed by the namer)
Commander Urist (...or other military-like titles, really an extension of the above, but dependant upon number of current followers and some sense of hierarchy this may indicate)
Urist One-<bodypart> (...hand, eye, leg, lung? ...or some other distinctive non-original feature that might lead to such as "Scarface", "Burnt-foot", "the Blistered")
Not forgetting some stranger titles that don't name Urist directly at all (c.f. The Lone Ranger, Zorro, The Shadow, He-Who-Shall-Not-Be-Named, The Green Knight, The Little Corporal, Little Boots=>Caligula, The Gathering Storm, Your Royal Highness, although there's many different ways for these other nominative descriptions to arise, including some degree of semi-randomness as well as history and equipment/clothing-details based).
Really, if fame among encountered entities is tracked by incident and not just as a "score", I could see a multi-choice procedurally-generated 'fame name' being encountered[2]. Which need not be positive. Something like "Urist the Slovenly" might be used by one who has heard of the many quests given to Urist, but knows that few (or none!) have yet been reported as successfully accomplished.
(I also sort of imagine that if Urist has killed an entire elven settlement with only the humans learning of it, and killed an entire human settlement with the only witnesses being a elven trade-group, he could be known as Elf-Bane by some, and Killer Of Humans by others, but then you get into dodgy territory whether such a "fame datum" from either side might cause problems if news of the fame spreads, perhaps by 3rd parties, between the camps. Will they not recognise the unknown title as relating to their own particular hero? Will the humans send Urist Elf-Bane on a quest to kill Urist, Killer Of Humans, and/or vice-versa from the elves? Actually, this extreme example disguises the fact that if fame tracking is not via omniscience, you might well get the Aragorn effect, with "Strider" being known only as a ranger or mysterious traveller by most, and only a few will know of the existence of a true heir to a certain kingdom and some of them might not know that this is the same guy, anyway, perhaps only by another name.
Anyway, my thoughts, for what they're worth. Some might be easy to implement, but I think some are a bit complicated for the current state of play.
[1] Understandable, given the "dwarfs/dwarves" alternatives throughout popular culture, for which I believe we have J.R.R. Tolkien himself to answer for.
[2] And, from its first randomly occurring utterance, forming part of the character's history, so that it's more likely to be heard again from entities in close communication with the original random-namer, and over time may spread fare and wide alongside with the current and even later tales of fame. And thus "Urist the Slovenly" might well catch hold and stick (albeit increasingly with the irony of "Little John") even as Urist proves to be a capable and speedy dispatcher of Colossi and Dragons and all manner of other enemies of the people. Each particular people.
[X] There's two deliberate errors left in this message, to try and sate the Pedant's Curse, but there's probably more. Excepting stuff like the ellipsis-initiations and parenthesisation of the commentaries, which was the best way I could think of writing this, even if is a bad style choice.