The other thing to remember, is that wizzies need a LOS for most of their spells. There are very few spells, other than summonings I suppose, which can turn corners or climb over the crest of a hill. Entrenchments could make most area of effect spells very difficult to use, as could fighting in any sort of area with cover - forests, underground, cities, etc. Sure the flying mage is good to go, but then again, he's also just painted a great big bullseye on himself. He'd better stay pretty high in order to stay out of reach.
Ok, perhaps my example of stone giants was off, but, then again, there are hordes of other critters that a nation could use to great effect. The fliers obviously, but also:
Animated objects for troop transports
Blink dog scout units
Any of the dire animals
Ooze or jelly siege weapon ammunition
Rust monsters!!!
Treants
Any of the above critters could be either bred and raised or enticed to join an army.
BTW, I read your demographics S'mon. 20 MILLION??? Touch on the large size don't you think? Considering even real world modern cities don't have that many people. How would you ever feed that many mouths. IIRC, at around the 11th century, there were two or three cities in the world over ONE million people. That's a whole lot of people.