Here's a little trick I use when coming up with fantasy sounding names. I'm not a big fan of the whole put as many apostrophes into a word you've designed to be as tongue twistingly unpronounceable as possible thing. And I don't really have the time to develop internally consistent artificial language after artificial language to create a believable linguistics. But you also don't want to go around having your high fantasy characters calling each other "Bob" and "Steve". Instead, I want things to be easily read and understood while, at the same time, evoking something a little exotic, a little foreign, maybe a little mysterious, but something different than plain old English (Although, you know, sometimes just going for straight descriptive English names – like calling a city by a dusty, clay filled mesa “Red Rock” can work.). So, here's what I do.
First, pick a foreign language. It helps if you keep all the words you come up for one specific area or people sounding like words from this language. Instead of a bunch of random words you have something that at least sounds like its internally consistent. There's value in playing against type, especially when you're dealing with cosmopolitan areas or lots of different culture who've occupied the same territory but that only works if everything else has a basic similarity.
For example, I'm basing my story in an ancient and proud Kingdom that's fallen on some hard times but definitely has the whole Medieval sword and sorcery flavor to it so I want something a little old school. I thought about going with old English or even that old standby Latin, but instead, since this place is somewhere on the periphery of the “civilized” world, I'm going to use something more Germanic. That's, to me, a lot of hard, gutteral sounds and long, complicated words but a sibilant sort of poetry within that harshness. I want to emphasize that lyricism so I'm probably looking for something in the Old German category, which is good because there's plenty of dialects – high and low. I've done this a bit and dabble in linguistics so I'm picky. But it could be as simple as saying “Yep, French it is for these guys and Japanese for those.” for you.
Second, pick whatever it is you want to describe. What is it? A person? A place? A thing? What's it about? What's it do? What's it role in your plot? What can you tell yourself about that object? Figure out what is is and then you can figure out what it's called.
Continuing my example, there's a valley in my script that's going to be particularly important. It's the site of – at the time my story is taking place – a famous, no an infamous, battle. See, my Kingdom's fallen on hard time's because it's been invaded by an outside force, some arrogant technologically superior, wide-ranging, continent spanning Empire that's slowly crushing the kingdom under their heel. They're a different culture and they get their own naming pattern, but the important thing here is that this valley is the site of the last stand of the kingdom's defenders. The last battle of their war for independence. The battle where their former king, a proud, virtuous, courageous man who led his people against the invaders and is generally considered an all around swell guy when those same invaders aren't in earshot – they have this thing where they pull out your tongue for talking ill about them so most people kind of stay away from the topic, at least in public – the battle where he was killed. The battle where those invaders won the war. And it wasn't just a loss on the kingdom's part, it was a slaughter, it was a massacre, it wasn't even close. It's infamous, it's a horrible memory for those people and it's a fresh one since it happened maybe 10~15 years ago as my story opens. That place needs a name because there's going to be plenty of reference to it. People talking about the Battle of Such and Such a Valley or how their former king met his end on the field at Such and Such a Valley. It's a bit of a codeword, then, for those in the kingdom who resent their invaders but haven't found a way to do anything about it yet. And, at the same time, a loaded phrase that conjures up memories and implications of a better time and a better place – when their land was free and their king was just.
Third, if you've done it right you should have a pretty clear idea about this object so pick one word to describe it. Just one word. Say, “Happy” or “Sad” or “Bittersweet”, whatever you think is best. But some word that has a meaning, even if it's only one that makes sense in the wider context of your story. If you don't like that word, find a thesaurus and look up some synonyms. Or translate it into your chosen language. Or even another one. Either way, find something that you think sounds nice and fits what it is you're naming. We don't tend to put a lot of thought into it in America (Remember that Bruce Willis line from Pulp Fiction: “I'm an American, my name doesn't mean anything.”) but most places, names have deep, associative meaning. The more meaning you can pack into your name, the more resonant it's going to be when your characters are using it. Calling someone “Bob” isn't as evocative as calling them “Valor”, is it?
Continuing the above, for reason that will hopefully soon become apparent, my chosen word is “verdant”. I like to be a bit subtle about these things but it's a word that means, to me, green and growing and wide flowing hills of grass stretching out as far as the eye can see. It's a perfect name/concept for a valley since it's one that conjures up images of a rich, beautiful land. One worth owning. One worth protecting. One worth dying for. And thinking about that beautiful valley pilled high with the corpses of dead soldiers after their slaughter would no doubt make the people of my fictional kingdom a bit wistful. But at the same time, another meaning for verdant is “inexperienced” like a greenhorn. It's a nice little twit of the dagger that this kingdom, that longing for the old ways is a fool's paradise.
Forth, take that word and start playing around with it. Drop letters, shift syllables around, change consonants, make every “e” and “i”, whatever you want. Transform that word until you come up with something that sounds good. Then, once you have something that sounds good, try and make it sounds like a word from your chosen language base. Play around with it some more. When you're satisfied, that's your name.
Starting with “verdant”, for example, I fish drop the “v”. It's a nice sound but I don't like the alliteration with “valley” and this name is going to be paired with “valley” almost immediately so the v's got to go. That leaves me with “erdant valley”. Which is alright – I like that opening “er” sound, but I think I can do better. I look up a sample of Germanic words (You'll find the most commonly translated work, for European languages anyway, is the Lord's Prayer. That's because the first thing translated and written down in most languages was the Bible and other religious works. But since, like a good Catholic school boy, I happen to know the old Pater Noster fairly well, it makes it easy to translate at least a few words and get a sense for a language.) and find – in Alemennic, a dialog of Old High German – that the word “erdu” means “earth” or close enough for my purposes. Similar dialects have similar words. Which is great, because that goes hand in hand with my “verdant” context even though, as far as I can tell, “verdant” has mostly Latin and French roots – think veridian, a color of green, for example. Messing around with it a bit more I come up with the following list of possibilities:
There's plenty to choose from there. Erdus has echoes of “Indus” which is a rather famous real world valley. Erdanube really hammers home the Germanic connection although it's a bit blatant, still, a bit of work and we could smooth out that roughness. Erd is nice and simple, really calling to mind the word “earth”. But, I think, at the moment, I like “Erdanus” the best. It just sounds portentous, sounds important. And I think it works best, meter-wise, with “valley” following it. Unlike the two syllable words, you almost have to pause and take a breath after that trailing plural sounding syllable. It emphasizes, phonetically, that this is a place to really sit and think about. And I think anyone stumbling across it won't have any trouble figuring out a pronunciation fairly close to how I'm saying it in my head – it's nice and simple enough that it's not going to trip anyone up.
Now, that sounds like a lot of work to put into the name of a place. This place is important and I think it deserves a well-thought out name since it's so central to the backstory. But, really, I can do that sort of thing in a matter of moments, and after a bit of practice, I'll bet you can, too. The best part is that coming up with a few possibilities for each name gives you some choices to use for later names – I might end up calling a character “Erd” or even “Erd-something” in my script now because I've established that, in this kingdom, the sound “erd” is an acceptable one. With a handful of names run through a process like this, you can easily fudge some others, if you're pressed for time.
Done right, you wind up with a name that's both understandable and carrying a bit of subtext. But one that you're not likely to have seen anywhere else before. At heart the technique is as simple as taking an existing word and messing around with how it's spelled until you get something fantasy sounding. But by putting a little bit of thought into it you can help develop your world into something both believable and fantastic.