The German term for "fairy tale" is "Märchen" - that's the diminutive form of the Middle High German word Maere, which means "report," or "news."

Here's an excerpt from the Encyclopedia Britannica entry on Märchen:

Märchen, plural Märchen, folktale characterized by elements of magic or the supernatural, such as the endowment of a mortal character with magical powers or special knowledge; variations expose the hero to supernatural beings or objects. The German term Märchen, used universally by folklorists, also embraces tall tales and humorous anecdotes; although it is often translated as "fairy tale," the fairy is not a requisite motif.

Märchen usually begin with a formula such as "once upon a time," setting the story in an indefinite time and place....

You might want to take a look at the Google Books Preview of a fascinating book titled Annotated Classic Fairy Tales, by Maria Tatar.