I'm glad I could help it's looking really good.

I should suppose scale is entirely up to you ... it really depends on the imaginary underpinnings of your fantasy map. What technology level do the people possess (do they have horseless carriages or horses or none of those, do they have long-distance communications)? What kind of people are they (giants, dwarves, elves, chupacabras...)? How rugged is the terrain (do the mountain symbols indicate mountains like the Urals or like the Himalayas)? These and other factors determine how large an area can be rulled effectively - though they're not absolute determinants.

If it's the size of the Mediterranean that's app. 2.5 million km2, or 5 Frances. Judging by that, I'd think your states are not too large - and besides, you can always make some of them loose federations or even confederations, and thus indicate an association of semi-independent poleis.

However, on a continent (island?) this small I'd warn against leaving much wilderness ... if the people are at least a bit human, they'd have settled as much as humanly possible!