Sorry for the update so late in the day; I was enjoying my day off. :)
I’ve already done a specific post on language, but mostly on things like not scattering apost’rophes in random places. This focuses on language construction, and some of the things you can do to make your language more non-human (mostly violating earth universals).
1) Have it be an object-initial language.
Language word-orders go in six separate patterns, all organized around three main parts: S (Subject) V (Verb) and O (Object). Earth languages with one of the two subject-initial word orders are the most common, as in English’s SVO:
The man(S) beat(V) the dog.(O)
Verb-initial word orders are possible, though rarer:
Beat the dog the man.
But Earth languages with either OVS or OSV word-orders (as a usual thing, not just some examples in poetry) are incredibly rare; some linguists doubt whether they exist at all. This could be a simple step towards creating a truly alien language for your fantasy world. A language that regularly says “The dog beat the man” but means the same as the English “The man beat the dog” could be easy to create while straining your readers’ minds appropriately.
2) Break common Earth rules about the placement of words.
Some linguists have noted that Earth languages which place adjectives in front of the words they modify are more likely to have prepositions, while the ones that place adjectives behind the words they modify are more likely to have postpositions. So:
‘blue dog’ is to ‘around the corner’ as ‘dog blue’ is to ‘corner around.’
This isn’t as spectacular a reversal, or as easy a way to set your readers’ heads spinning as the object-initial word order, but it does mix and match in a way that could be your alien creatures’ own.
3) Create new cases.
Fantasy languages using case (word endings that indicate grammatical or spatial relationships to their noun) like Latin or Finnish are fairly rare, perhaps because a lot of fantasy authors speak English, which makes scant use of cases. However, we still use separate forms of ‘he’ to indicate whether we’re talking about the subject of the sentence, the possessive (his) or the object (him). Pronouns retain new cases longer than most other words because they’re a hard group to break into, one reason that it’s also really hard to create a new, widely-accepted personal pronoun meaning “he or she.”
Perhaps you have a fantasy language that has a unique system of pronoun cases. As well as forms for subject, possessive, and object, there’s also one that people who have been away for a long time can use to refer to the person they last saw, so that a sentence like “I saw him [person who is new] and him [person whom I saw last time]” would be wholly distinct and easy to understand in your alien language.
Pronouns aren’t the only words that can have unique cases, though they may be easiest to start with. Perhaps your shapeshifting race has a set of cases that describe the distance of the human body from the animal one, or the direction they move in (surely not a direction visible to anyone else) when they shapeshift. Perhaps dwarves’ case-heavy language talks about various distances underground, or the elven tongue talks about various distances up trees. It’s a way to insure, above all else, that your alien language doesn’t simply translate word for word into English.
4) Incorporate gestures into your alien language.
Unicorns may be limited in the number of sounds they can make, not having lips or tongues nearly as flexible as a human’s, but perhaps they can change the colors in their horns, or add gestures from their ears and tails to the conversation. This would make a system of writing more difficult, but then, writing in general would be difficult for unicorns, so they might not mind it.
Don’t limit your alien race to words that best fit human mouths, or similar-to-human mouths in the case of elves and dwarves. If they have appendages like tails that humans don’t but which they can move freely, these should be added to the conversation. Nor should human gestures be translated simply by copying, such as a dragon moving its paws emphatically. Come up with something that would fit the species, like the dragon flickering a tongue or twitching an ear for emphasis.
5) Create unique “kinship groups.”
Many languages are extremely rich in terms for a particular thing, such as the Yiddish language being rich in terms for family members. This doesn’t necessarily mean they have bigger vocabularies than other languages, though, since the richness in one group means they may be paltry in something else (English is extraordinarily rich in ways of forming adjectives, but adverbs are clunkier, and the -ly group dominates them).
If you have a non-human race with an especially important or persistent type of magic, then the new group of words might focus on that. I use an empath race, the land Elwens, who can feel different types of emotions as different physical sensations, and so come up with different words for the emotion that in English is covered by the single word “love.” There’s cylmansha, love sweet and strong and calm as a summer’s day- like platonic love, but it can have a slight romantic component, too- and ryal, violently passionate love that is likely to get you killed, and many others. When they try to learn other languages with less emotional terms, land Elwens often feel blind and confused as to which word is best. On the other hand, they themselves are vague about physical objects. “Yanne” is chair, seat, or throne as needed.
Bottom line: Build your language off the way your race sees the world. If they can hear the stones talking, verbs relating to that are not off, but it would make no sense if the same race never built with wood and lived at a distance from the forests and yet were aware of all the different kinds of trees.
6) Use some of the tricks of Earth languages that are not related to your particular tongue.
This will help insure that you’re not sneaking English’s best (and worst) features into the new fantasy language without realizing it. There are plenty of tricks in Earth languages that aren’t duplicated in English; just look in any linguistics books.
For example, there are some languages that use an identic case, meaning that the object case-marked is being said to be the same as, or similar to, something else. “You’re the same as your father” might get worded as “You’re father-same” in a language with an identic case, where the case is attached to the noun “father.” It provides a subtly stronger and more emphatic meaning than the same sentence in English.
There are also languages (among them Native American languages) that use switch reference. This avoids the complications of English sentences like “I saw Bob and Daniel come out of his house.” Someone reading this without further clues has no idea whether it was Bob’s house, Daniel’s house, or the house of someone else previously mentioned. Languages with switch reference and the “fourth person” could use a unique “his” pronoun to let the reader know it’s the house of someone else entirely.
Pronouns also could be revamped. There are many languages that have dual forms of pronouns, such as “we two” alongside “I” and “we.” There are others that have inclusive and exclusive forms of we, so that one pronoun means “you and I” while the other means “me and these other people, not you.” Or you might drop pronouns altogether from one set of their functions. This is what I did with the land Elwen language, Aril; it’s so heavily inflected that subject pronouns vanished, leaving only the inflected verbs with their personal endings.
I don’t think making a language that’s convincingly alien is as hard as people think- especially when a lot of fantasy languages are English or Tolkien clones. *sigh*