I think demonyms more often come from the place the people are from rather than the leader. Imagine yourself living hundreds or thousands of years ago, and some new people arrive in your village. Chances are, you have no idea who the leader of their original home is - but you have a rough idea of where it is and what you call that area of land. So you refer to them as the "people from Land" or "Landish".
So the question really comes down to where place names come from. When you dig down into the etymology of names, a lot of them have a meaning in whatever language was spoken by the locals at the time it was named, and they're often really simple, referring to literal, physical attributes that can be recognised. Then what happens is the name stays the same even when the rest of the language moves on.
You can also get land areas that become named after the people that live there, creating a circular case where the people are named after the land but the land is named after the people. This is the case for the demonym and toponym for where I live. The place Cornwall roughly means "strangers/foreigners of the horn" or, essentially, "horn with all those weird people in it", where the horn refers to the shape of the land, and the "strangers" part refers to the massive cultural and linguistic difference between the Anglo-Saxons in the south and south-east of England and the Celtic population in the south-west. The demonym "Cornish" therefore directly translates as "from the horn", but since it's also just a shortening of Cornwall (because "Cornwallish" would be a nightmare to say), one could say that "Cornish" is referring to "people from the horn with all those weird people in it".
I imagine if you dig down deep enough into demonyms, you'll find a surprising amount of them ultimately translate to "them weird people that live over there".