[fogihujy]

Well, there's been a number of very large bird and reptile species that humanity has been in contact with since the dawn of man. Many of our forefathers were rather small compared to modern humans, and a gigantic serpent or amphibian would probably be outright terrifying for small early humans armed with rocks and spears.

I'm not sure about genetic memory, but human oral tradition is very old, and while I haven't heard about any evidence suggesting it predates modern humans, I wouldn't be surprised if there are stories that turns out to be as old as human language is.