One of the coolest things about writing fantasy is that you get to create names for your characters and locations completely out of the blue.
One of the worst things about writing fantasy is that you must create names for characters and locations completely out of the blue.
Contemporary writers have this problem, too, as they try to name their own characters, even if they have a ready list of normal names in their chosen environment. I think we all have certain phonemes (unit of sound) we gravitate towards. Until I started writing, I had no idea how much I liked names that began with a hard C and/or ended with an AR sound.
There were several others I had to alter because they were all sounding the same. If you find yourself doing that, don't stress. It's easy to change them using the "find and replace" function in Word or Scrivener. And you don't even have to have real names while drafting if you just can't find the right ones. In The Traitor's Kiss, I think I called D'Amiran "BADGUY" for three whole drafts. "Concordium" was a place holder name I wasn't originally keen on, but grew on me and stayed.
When deciding names, I have few simple tools:
The Atlas is a simple one for non-English sounding names, and I also use it for scaling in my geography. If I can think of a country or territory as the size of Ohio or Texas, then I've got something real to compare it to. But if you want an African or Asian sounding name, flip to that continent and look at the places. Then tweak them by rearranging syllables or swapping out letters.
Take inspiration from Latin and Greek, plus other languages. J.K. Rowling did a lot of this, but I do it more sparingly. Translation websites are great. At www.indifferentlanguages.com you can enter a single word and get it in over 30 languages. Take your pick!
As an example of some that I have used: Concordium comes from Latin (con=together, cord=heart -> bringing hearts together). Sagitta means arrow, and that is the name of a triangle shaped crossroad on my map. Catrix is Latin for scar, and that is the name for the mountains which rise up in the middle of the nation like a scar on the landscape
You don't have to be fancy about everything. I have a "Northern Road," an "Eastern Strong," and a "Western Strong," plus Northern and Western Seas. The good thing about those is that it makes it pretty obvious to the reader where those things are. Don't be afraid to have a few super-simple sames like Al or Joe or Sue. It can be a small point of comedy in word of fantastical, complicated names.
Use a Baby Name Book like you would the atlas, either by searching for real names with cultural ties or meaning or ones to tweak. Mash names together.
Use/create a cultural norm. Many European names like Miller, Smith, and Cooper are based on occupation, giving the added benefit of telling your reader instantly what this character does. In the Song of Ice and Fire series, certain names in each region denote illegitimacy, hence Jon Snow.
Use a character's backstory. Sage was named after her mother's favorite herb, even though the name of a plant implies she's illegitimate in her society (which she isn't, her parents just didn't give a crap about that sort of thing). My character Casseck only goes by his last name (or Cass). He was a second son, and his older brother was named for their father. There was such a long time between the two that his parents assumed there would be no more sons to name after grandfathers, so they gave Cass a first name that was a combination of both. I went to the baby book and picked the two worst names I could find and mashed them together. Ethelred + Aldregon = Ethelreldregon. Poor kid.
Lastly, to avoid repetition, I suggest keeping some sort of central list. The little booklet in the picture is mine for the Traitor's Circle series, but you can have a file in Scrivener or Word or even use an actual address book. Then you can see that you are getting pretty heavy on certain sounds or consonants-especially the first, which is what hits the reader first. When choosing a name for a Demoran prince, I didn't want anything outlandish, and I noticed I had almost no names or places that started with N, and most of my characters had one or two syllable names. Boom. Nicholas was named.
Do keep in mind that fantasy has a not-so-great reputation for incredibly complicated and unpronounceable names. I've heard of readers dropping a book they were considering simply over the horrible names they saw on the first few pages. Do your readers a favor and make the names easy to figure out, or at least provide a glossary.