Naming usually comes last for me, its often based on what I want the land to represent (read: what is in the land) and if I can't think of anything personalized, I will take a Tolkein-y move and mesh languages (right now Im on a Mongolian-German mesh).

For example:

Land's economy is fishing based: The towns might be named something like Teem, Rot's Cove, Sailorhill or something generally fishing and nautical based. While the region may have a more creative name based on an imagined history.

or

Islands of the Land's shore are being invaded by demons from another realm -- the landmarks in that area will have names based off the demon's language (here it might be good to mesh languages) while the lands around those islands will tell about their nature of always defending against hordes of demons. Such as: Rykyan's Bastion, or The Walled Coast, or Fleetguard.