I like that idea. So basically it could be a two-step process. You first generate a land mass that you like, and then define regions within that map.
Once regions are defined, the program could randomize the borders, so they are not perfectly straight either. And the user should be able to select specific places, and randomize the name for only that place specifically (so you can get rid of names you don't like).
Since it's processing of a map, most of this can be done automatically too. Very basic feature detection, maybe on the level of "select similar" tool in a raster editor.
You define which area is The Shire, and which are is Mordor, in a manner of speaking. Each area follows different naming conventions. The land of the big bad has names that sound menacing. And the land that is peaceful, has names that sound like typical rural English town names, for example.
Naming map features implies several layers of data, and doing anything beyond connecting two with the third requires extra steps. Something like this:
1. Map (given - generated). Presumably pure raster graphics, vector is possible, but unlikely.
2. Name generator set of rulesets (given - by the user).
2.1 While you are deciding on it, choose which sort of names is fit for mountains, which is fit for towns, etc. You may want to have some way to filter the list.
3. Geographical features - shapes, borders, etc (detectable - created from the map).
4. Logistics difficulty map (may benefit from user input or need tweaking to have desired result) - people used to measure routes in "days of travel", and why wouldn't they? Mostly this means marking possible roads and appraising region borders for how hard it is to run war or trade across them, and how much contact people have in general. Which makes it more important if the "people" steps are automated. It looks like geographical level, but it depends on things like terrain capabilities of animals and seaworthiness of vessels.
5. Regions. (requires some user input or tweaking to have desired result). It's the main "people dependent" layer.
5.1 Basic assignments - that's where "which is The Shire, and which are is Mordor" is set. This finally links the map and toponym list.
5.2 Merging of the major regions - e.g. you decide all those connected valley/low hill lands are "The Shires".
5.3 Divergence and adaptation. The previous steps may suggest various issues, including where the different Shires are and how much they are likely to diverge - i.e. if the North-Western Shire has a border with swampland, it may have to deal with some problems from mosquitoes to alligators to trolls. And if the Southern Shire is stuck in a big river delta and is directly connected only with Green Shire upriver, you may want to consider how life here is going to differ from low hills of the Middle Shire, and how much events in the thrice-removed North-Western Shire can possibly affect it.
6. Exceptional features (requires some user input or tweaking to have desired result).
6.1 There's likely to be a town on that river/coast, or a battle site in that valley, but where exactly?
6.2 Roads and trade routes, since they depend on such point locations, on relations and on warping by logistics difficulty - all the previous steps.
...Repeat 4-6 to reflect participants being wiped out, shrink and fade into obscurity, merge, expand, split to create several new ones. Or just "shaken". This produces various ruins and toponymical anomalies like "foreign" or "bastardized" names - "Elves don't live here, but they used to".
