20K is the population of a large and powerful city in the medieval era, but not the population of a powerful country.
20k would be significant, but not near a powerful city - more of a regional power at best.
Powerful cities would start at 100k and above. Check
here.
Not sure, though, if medieval times have anything to do here - it should be more like the Collapse of the Bronze Age or the Iron Age. To be fair, the whole lore is a mix of completely different cultures spanning something like 2,000 years, if not more, so comparisons are quite hard.
Rome had a population of around 100k when it began expanding (First Punic War), so an estimate of 50k to 80k might be reasonable - as Winter City starts/tries to. This is just a historical perspective, not a lore-based one. And they have magic so who knows.
Note: cities in the past were not as clearly divided from the countryside as they are today. Every "city" in reality comprised both the city itself and the surrounding countryside, including villages, as both were interdependent and could not thrive without each other.
Second Note: In CoC2 both land and populations are pure fiction - you quite quickly will be in situation of too much, too big, too close and too powerful. In the "real world", Winter City and Khor'Minos would likely conquer each other, or at least both would conquer everything in between. The amount of independent political entities in so close vicinity is quite unrealistic.