The problem with names in fantasy is a subset of the more general problem of Diction. Names have convincingly to derive from another time and place but also bear some sort of appropriate association.
One solution is to use words not usually used as names, but which bring with them verbal force – e.g., Mervyn Peake's Gormenghast trilogy has characters called Flay and Swelter – or to assemble names on a portmanteau principle – Peake, again, has characters called Prunesquallor and Steerpike, while the giants in Stephen R Donaldson's Chronicles of Thomas Covenant the Unbeliever (1977-1983) have names like Saltheart Foamfollower.
Names which are simple statements of allegorical meaning – Sweet Rhyme and Pure Reason in Norton Juster's The Phantom Tollbooth (1961), for example – are appropriate to Wonderlands; names that tend in this sort of literalist direction are less appropriate in a Fantasyland context.
Invented languages bring their own problems. J R R Tolkien was perhaps the only writer of fantasy with sufficient expertise to conceive both consistent languages and names deriving from them, but even he notoriously hits some dangerous false notes and crudities. He may not have intended the dark riders, the Nazgûl, to be read as a portmanteau of Nazi and ghoul, but that is inevitably how they have been read; his Dark Lord Sauron has no obvious connection with the reptilian, save those intrinsic to a Devil-figure in a Christian Fantasy – the Old Serpent. Tolkien used a mixture of procedures: many of the names in The Lord of the Rings (1954-1955) are archaic names from Northern European languages – not entirely inappropriately, since his Secondary World is clearly intended to be at least partly cognate with Europe. When he does use portmanteau names, it is by assembling syllables that have connotative force rather than by putting words together – Tom Bombadil for example. It is significant that he was prepared to abandon portmanteau names – Tinfang Warble is a notorious example – that on reflection and redrafting struck him as inherently silly; it is also significant that even Tolkien, who had thought long and hard about the issue, had trouble with names.
As with the more general case of diction as a whole, the only way to be sure-footed in the matter of fantasy names is to be linguistically sensitive. Jack Vance's names draw eclectically from various sources of invention, but they feel right because they are integrated into his wayward style and odd touches of recondite learning. Terry Pratchett draws on the same battery of sources for fantasy names with equivalent skill, often engaging in elaborate jokes in the process – the Patrician, autocrat of Ankh-Morpork, has the family name Vetinarii, by analogy with the Florentine Medici (vetinarii = veterinary surgeons; medici = doctors).
It is generally assumed in fantasy that names have magic (> True Names). [RK]