About the phoenix in 1 Clement, the description given corresponds closely in detail with the accounts of Pomponius Mela (Chorogr. 3.8) who wrote in AD 40/41, and Pliny the Elder (Nat. Hist. 10.4), who wrote before AD 79 (as he died in the eruption of Mount Vesuvius). A few of the other details are found in later writers dependent on earlier sources. All this suggests that Clement's tale is essentially Roman in origin, which is what would be expected if the epistle was written in Rome. Here is a detail by detail comparison:
from Arabia (Clement, Pliny)
a unique specimen (Clement, Pomponius Mela)
lives 500 years (Clement, Aelian, Nat. animal. 6.58)
coffin of ... myrrh and other aromas (Clement, Pomponius Mela, Pliny)
decomposes (Clement, Pliny [< citing Manilius])
worm emerges (Clement, Pliny)
grows wings (Clement, Pliny [fieri pullum])
to Egypt, Heliopolis (Clement, Pomponius Mela, Pliny)
by day in the sight of all (Clement, Johannes Lydes, De mensibus 4.11 [< citing Apollonius of Tyana])
altar of the sun (Clement, Pomponius Mela, Pliny)
priests check records (Clement, Aelian, Nat. animal 6.58)
RunningMan....I have to disagree with you there about "unicorns". The use of "unicorn" in the KJV is due to the Latin being influenced by the Septuagint rendering, which translates Hebrew r'm "wild ox" as monokerós "one-horned". These terms were indeed used to described mythical equine creatures in classical literature (cf. Ctesias, Indica [< cited in Photius, Myriobiblon 72], Pliny, Nat. Hist. 8.31, Aelian, Nat. animal. 3.41, 4.52, Vita de Apollonius Tyana, 3.2), however there is no evidence that the original Hebrew term referred to the same thing; none of the details mentioned by these other writers occur in the OT use of the term r'm. There are passages like Deuteronomy 33:17 which directly conflict with the LXX rendering: "As the firstborn of his bull (shwrw; LXX tauro), majesty is his / And his horns (qrnyw; LXX kerata) are the horns of the wild ox (r'm; LXX monokerótos)". Rather than being equine, the beast is likened through literary parallelism to an "ox" and rather than being one-horned, the r'm has plural horns (in fact, two horns since the horns are likened to the two tribes of Ephraim and Manasseh in the next sentence). Moreover in other related Semitic languages the term is used to refer to oxen, especially Akkadian rimu "wild ox".
S.R. Driver in his commentary on Deuteronomy presents evidence that Hebrew r'm and Akkadian rimu referred to the Bos primigenius species of oxen, one of the Pleistocene megafauna known to the Germans as aurochs and which were partially domesticated in Mesopotamia about 5000 BC and which became extinct by 1627. For instances, Bos primigenius teeth have been found in the same valley (Nahr-el-Kalb) where Tiglath-Pileser I (1120-1100 BC) claimed to have hunted rimu. It is also possible that as populations of aurochs dwindled and as their average size decreased over time, memory of larger aurochs took on mythological proportions; the "Bull of Heaven" in the Gilgamesh Epic might be one example of this. The OT references to the r'm stress their strength, size, formidable horns, and wildness, which are probably still appropriate for Bos primigenius but which may also conceivably draw on an intensified conception of a beast which no longer was as common as it once was.