Also note, that most of them were not fighting at the same time. Simple logistic and organizational issues make it impossible - there is a lot of terrain, true, but even more bottlenecks, like bridges, roads, junctions, impassable terrain (dunes, lakes, swamps) and so on.
So, every province should have limit of units that can fight with full effectiveness, then each unit over the limit should suffer from some sort of penalty (either negative combat modifier/higher supply consuption and so on).
This limit can be somehow connected with infrastructure of the province (and it's size off course) - it will also make infrastructure upgrade a bit more useful then now.