Genghis Khan, Alexander etc. are rulers who had kingdoms which were larger than most of the countries now. How would they have ruled their countries efficiently when it would take weeks for information from one place to reach another. For example, if unrest broke out in a far corner of their kingdom, wouldn't it take longer for them to hear of it and longer still to quench it?
The answer to this question depends somewhat on the kingdom, geography, and era. The ancient Achamaemenid Empire of Persia (Iran) was arguably the first true empire in history, and spanned a sizeable amount of territory. It made use of regularly stationed outputs with stables always containing well-fed and well-rested horses, for messengers to quickly get around the empire. Combined with a primitive road system (which the Romans used to excellent military and economic advantage in their later empire), this ensured good communication and administration of the kingdom. Alexander the Great, having conquered Persia in the 4th century B.C., inherited this network of roads and indeed learned from the Persian method of government. In addition, the sub-division of an empire into smaller regions, run by local rulers or trusted generals, led to early top-down bureaucratic forms of rule that worked quite well. For Alexander the Great and the Macedonian Empire, these rulers were "satraps"; for Rome they were provincial governors.
In summary: the combination of regular stationed outposts (garrisons for the army, and trading/tax collection stations), and the pyramid-like sub-division of territories for administration by petty rulers and officials led to a, while often fragile, fairly efficient and manageable form of impirial administration that worked for the Persians, Macedonians, Romans, and later the Mongols.
Usually the ruler would divide the kingdom up into smaller territorries and appoint someone to be the leader for that territory. This has historically been a pretty common practice. From the Zhou Dynasty in China to the Roman Empire we can see examples of this. In addition, when you look at medieval kingdoms in England, France, and Germany, the monarchs appointed Earls and Dukes and such to maintain control over portions of their kingdom and to ensure loyalty and support.