Names from Prester John's kingdom
In the 12th century, an emperor known as Prester John (Priest John) wrote a letter to the courts of Europe begging for help in defending his country from infidels. He told of the wonders of his land, filled with rivers of precious stones, flocks of magical creatures, and all manner of miraculous things, a true medieval paradise:
Our land streams with honey and is overflowing with milk. In one region grows no poisonous herd, nor does a querulous frog ever quack in it; no scorpion exists, nor does the serpent glide amongst the grass, not can any poisonous animals exist in it or injure anyone.
The letter prompted a surge of exploration that lasted a good two or three centuries before it petered out. In that time, people looked for Prester John's kingdom in India, Tibet, and Abyssinia (Ethiopia). Even after the search died down, Prester John's kingdom continued to appear on maps; it didn't disappear until the late 17th century.
The legend of Prester John spun off few but colorful names:
Place Names
Golbache
Hermes
Ind
Mistorak
Nyse (or Nysa)
Pentexoire
Susa
Zone
Personal Names
Gatholonabes
Gundoforus
Names of Beasts, Plants, and Magical Objects
assidos
nudiosi
psittake
Cannibal Tribes' Names
Agit
Agrimandri
Alanei
Anie
Azenach
Befari
Casbei
Conei-Samante
Fommeperi
Gog
Magog
Vintefolei
Further Reading
Translations of the Letter of Prester John: a modern translation, the 1892 translation by Robert Williams, and Latin for the hardcore enthusiast.
Medieval Sourcebook: Mandeville on Prester John - Sir John Mandeville's entertaining embroidery of the Prester John story.
Medieval Sourcebook: Otto of Freising on the Legend of Prester John
Mythical Geography: Kingdom of Prester John - Period maps of Prester John's kingdom.
Wikipedia: Prester John - A comprehensive Wikipedia article on Prester John.
Prester John - A cheerfully snarky take on the Prester John myth and the controversy surrounding it.
The Kingdom of Prester John - A page that claims that the letter from Prester John was not a hoax, and the Kingdom of Prester John was an Indian empire known as Sanfotsi or Zabag.