Tolkien didn’t invent the fantasy genre, but he defined its modern incarnation. Everything is sub-Tolkien, or post-Tolkien, or a reaction to Tolkien, or consciously not-Tolkien. He’s inescapable.
Of course, Tolkien’s goal wasn’t writing fantasy per se. He wanted to create a mythology for England, and a home for his invented languages. He had a genius for names, drawn from his experience with history and philology. He borrowed names from the sagas (all the names of the Dwarves – and Gandalf – are taken from the Dvergatal, the Dwarf-Tally) , or created them using his own languages, or from the rules of linguistic evolution. They work – they feel part of the world, grounded and real and plausible.
And that’s hard. What do you do if you’re not Tolkien?
Borrow from History: One of my favourite resources in all the world is the Onomastikon, a list of historical names. I also rely on Behind The Name when writing material set in the modern day. Pick an obscure, long-vanished culture and take names and inspiration from that.
Tweak: Adjusting commonplace names gives a familiar, low-fantasy vibe. Jon Snow – prophesied hero of Song of Ice and Fire, or Channel 4 newsreader? Bob the Barbarian doesn’t sound right for a fantasy hero, but Rhobe might work.
Hats and Epithets: Adding a title (Captain, Duke, Pope) or a nickname or epithet (The Marvellous, Axebreaker) gives the reader an easy handle on the character.
Make Sure Humans Can Pronounce It: One of the infamous sins of fantasy writing is sticking in piles of ex’tra’neous a’postrop’hez and excezzive uze of curiys speeling. Don’t.