I'm trying to imagine this : A kind of powerful (and of course beautiful, what would a sorceress be without this cliché ? ) is wandering around … And makes herself a name by defending all men's grabs by doling out headbutts …

The next week this town is filled with lots and lots and lots of men complaining about a massive headache, meanwhile the women of the same town laugh …

And so this name was spread … And even further by some mercenaries/adventurers/travellers who are journeying to other parts of the country, thus spreading the word (just slightly exaggerating it) of the "mighty sorceress of 'S'makh-Daon' " …