I kind of feel like OP is cherry-picking examples of some of the best-drilled (a.k.a fastest marching) armies in history at their top speeds (so most likely in perfect conditions/terrain, or being forced marched, which is already in-game), which I don't think gives an accurate picture of how fast armies should actually move.
The Mongols shouldn't really be included because steppe nomads 100% on horseback (of hardy steppe horses, bred for traveling long distances with a rider) can obviously move really fast. Perhaps hordes should have some sort of bonus to cavalry movement speed to simulate this.
Marching 15km (9 miles) a day does not sound unrealistic or slow to me. Having done a decent amount of wilderness backpacking myself, I can tell you that 9 miles a day over rough terrain carrying 50 pounds of gear leaves you pretty tired, and that's without the additional complications of coordinating the movements of 20,000+ people. The average army was not as well-drilled as the examples mentioned, and particularly in the early days of the game, the army would likely be supplemented by poorly trained peasant levies, who would really slow things down. Maybe army movement speed should scale a bit with tech, but no army in game should be consistently going 40km a day unless you're force-marching them. Keep in mind that Napoleon ended up taking a butt-ton of attrition when he tried to move that fast through Russia.