Other names are: Asp Turtle, Aspido-chelōne, Aspidochelon
The Aspidochelone is a sea monster, described already in ancient tales. It has the form of either a large turtle (in eastern tales) or whale (in western tales).
Tolkien himself provides some etymological explanation in his Letters:
|The poem on Fastitocalon is not like Cat and Oliphaunt my own invention entirely but a reduced and rewritten form, to suit hobbit fancy, of an item in old 'bestiaries'. I think it was remarkable that you perceived the Greekness of the name through its corruptions. This I took in fact from a fragment of an Anglo-Saxon bestiary that has survived, thinking that it sounded comic and absurd enough to serve as a hobbit alteration of something more learned and elvish – according to [a] system whereby as English replaces the Shire-speech so Latin and Greek replace the High-elven tongue in names. The learned name in this case seems to have been Aspido-chelōne 'turtle with a round shield (of hide)'. Of that astitocalon is a corruption no worse than many of the time; but I am afraid the F was put on by the versifier simply to make the name alliterate, as was compulsory for poets in his day, with the other words in his line. Shocking, or charming freedom, according to taste.
He says: þam is noma cenned/fyrnstreama geflotan Fastitocalon, 'to him is a name appointed, to the floater in the ancient tides, Fastitocalon'. The notion of the treacherous island that is really a monster seems to derive from the East: the marine turtles enlarged by myth-making fancy; and I left it at that. But in Europe the monster becomes mixed up with whales, and already in the Anglo-Saxon? version he is given whale characteristics, such as feeding by trawling with an open mouth. In moralized bestiaries he is, of course, an allegory of the Devil, and is so used by Milton.
The line of Old English text Tolkien is here referring to, is from a poem in the ExeterBook?: The Whale  (A Modern English translation by R.K. Gordon can be found on the same site ).
See also: ThisWiki:Fastitocalon