I've been sketching a bit on a conlang for one of my stories, and I began with thinking a bit on the sounds and structure of the language. I went for a tonal language, which makes it an information dense language. Then I decided on the basic grammar. Different languages have different orders for verb, subject, and object. In this language, subject and object is decided by a prefix, so it can be put in any order. Emphasis is made by putting something earlier in the sentence. I also decided to go with it having almost no inflections.
I have only created words so far for conjunctions and the particles/prefixes for subjects, objects, and verbs.
My idea is that the language will have "stem-words" and "compound words". Say that wet and air might be stem-words, but combining them in the right order, wet-air, would mean fog.
I'm not saying what I'm doing is good or recommended, but there is a lot more to a language than just the words.
When it comes to Tolkien, as I understand it, he made Elvish by taking Finnish and replaced the words. Finnish grammar is very different to the majority of the European languages, so a lot of the heavy lifting were already done.