It actually wasn't. The entire point is that becoming Genghis Khan meant he had to upgrade his primitive tribal government and become king, which is sort of what you're trying to do in the game...
In another timeline, the mongol conquests have never happened, because Genghis' subjects kept objecting that he's got more warriors than the ancestral other honor prescribes, being stronger than other tribes is against the mongolian ways, and he must split half of his lands and people into an independent rival gang at once because reasons.
Thanks for pointing out the exact problem with Norfleet's argument. Historically, there are usually two ways for a tribe to become a kingdom, and both of them involve getting a high enough population. One is by settling down, start emulating agricultural civilizations before them and grow their population the normal way. This process normally takes hundreds if not a thousand years. The other one is by conquering neighboring tribes. Once they are about twice as strong as any other tribe, they would start sending emissaries to the nearby tribes to demand their subjugation. Sometimes they just roll over, sometimes they would unite and fight back, but most of the time the neighboring tribes would still fail because one tribe of 1000 people who share the same blood, same language, same culture is >>>> 3 tribes of 500 people each who only band together at the last moment.
This is almost exactly what happened with Genghis, except that his case is a little to the extreme side of things, but not by much historically if you compare to other tribes (some even devour the flesh of their enemies to "gain their strength"). Every time after defeating a tribe, Genghis would round up the whole tribe, kill males above the age of 12, and then integrate the rest of the tribe. He did this until he conquered the entire Mongol Steppe. Also, keep in mind that Genghis never reformed his tribe into a Kingdom in any sense of the word. It wasn't until his grandson Kublai Khan took over that the tribe became a real kingdom in the form of the Yuan dynasty.
Now this is a fantasy setting, and I'll take that into consideration, but I think that warriors complaining about the tribe is getting "too big" still doesn't make any sense. It's actually a REALLY, really good thing, especially when food is plentiful. Normally, tribes would have a big celebration when their group is apparently doing so well, instead of complaining for no good reasons. A bigger population means power, prestige, and most important of all, security. A more realistic approach would be to expand the government to accommodate the newly acquired population. (Though not to the extend of reforming into a kingdom, that's a LONG way off. More like just shifting guard duties or who goes on the next hunt so nobody will bicker, that sort of thing)