Bird Myths and Legends
I ended up finding an article written by Rosemary Drisdelle. She lists a few myths like how in the Middle Ages, some thought that birds actually fly to the moon for the winter. She goes on to explain that this might have been due to birds like Bar-headed Geese that fly at very high altitudes.
She also writes that some Egyptians believed wagtails rode on the backs of storks and cranes to get across the Mediterranean Sea because it was thought that these smaller birds could not make the journey one their own.