Here's how I generate new names:
First principle: Have a language theme. Languages tend to have a unique sound, and often have their own little quirks. Examples include the German tendency to compile words (there was one word that described in intimate detail the professional life of a Danube river captain), the Japanese syllable alphabet, or the context-variable letters in one language I created for an alien race. The sound itself can be based on an existing culture or an emotion - or you could mix two together, like the ankkheris I created who speak deep in the throat and have vaguely Asian/Russian words. Ankkheris features lots of khs. Kiamakhal is their equivalent of 'bye'.
Second principle: Consistency. It's tricky, but if you come up with a few pieces of language they're easy to tesselate into new topics. And you can easily compound them together in new ways to create distinctive words. German is a very good basis for this, and you can do it with any fantastic language (after all, you're making the rules; might as well make 'em easy).
That's about it, really.