They are both acceptable as nouns, although if you want an adjective it would be fairy-tale or fairytale (eg a fairy-tale/fairytale romance). Both forms are given in the WR Dictionary (= Concise Oxford Dictionary).
Both are equally correct and so is the third alternative fairy-tale. There is rarely any one correct answer for simple noun + noun compounds like this: in English, it just doesn't matter much which you write.
I find dictionaries very helpful when checking spelling.
The American Heritage Dictionary and the Concise OED agree that the noun fairy tale is two words. It can also be an adjective (modifying "romance", for example); that's one word, fairytale, in the US, but hyphenated, fairy-tale, in the UK.