Wordorigins.org

No, a nightmare is not a dream about a scary horse. The origin is straightforward, but not obvious to the modern ear. The first syllable is easy, it is the same as the word night. It’s the mare part that makes people think that nightmares have to do with horses.

The word nightmare makes its appearance c.1300 in the St. Michael (Laud) manuscript:

Þe luþere gostes...deriez men in heore slep...And ofte huy ouer-liggez, and men cleopiet þe niȝt-mare.
(The wicked spirits...injured men in their sleep...And often lay on top of men, and men called them the nightmare.)