The real etymology is lost, I am afraid, but various speculations have been offered since antiquity and continue to this day. In Egypt the tree was known since at least 2600 BC. Egyptians already used the same name ('Bennu') for the bird and the date fruits. Bircher in The Date Palm A boon For Mankind speculates as to the reason:
"This bird was found on the mural paintings which decorate the tombs of the kings and the nobles, this bird was assimilated to the great 'Sun-God' 'Ra' and the sun itself. The terms 'Bennu', 'bnr', 'bnr.t' were also applied to the date palm fruit and to everything sweet. The date palm was linked in ancient Egypt to the sun-bird and them giving both the same name indicated the importance of this tree to their life (Bircher,1990)." [quoted from Alchemy in Islamic Times]
"Phoenix" was the name the father of botany, Theophrastus, gave
the palm tree (although he was describing its Cretan species rather than the dactylifera). Most scholars suggest that it was so named as "the tree of Phoenicians", who widely used it as a sacred and national symbol. But it is unclear if Theophrastus was adopting a name already in use, or if the bird's name predates him or the tree's, or whether he was thinking of the bird when naming the tree. The Egyptian mythical bird was presumably so named by Greeks for the palm's ability to recover after fire damage. Or so says Pliny (the Elder), see Zaid and de Wet, Botanical and Systematic Description of the Date Palm:
"The botanical name of the date palm, Phoenix dactylifera L., is presumably derived from a Phoenician name "phoenix", which means date palm, and "dactylifera" derived from a Greek word "daktulos" meaning a finger, illustrating the fruit's form (Linné, 1734).
Another source refers this botanical name to the legendary Egyptian bird, "Phoenix", which lived to be 500 years old, and cast itself into a fire from which it rose with renewed growth (Pliny, 1489; Van Zyl, 1983). This resemblance to the date palm, which can also re-grow after fire damage, makes the bird and the date palm share this name, while "dactylifera" originates from the Hebrew word "dachel" which describes the fruit's shape (Popenoe, 1938)."
Bircher speculates that the fruit color might have been a factor:
This region [Phoenicia] was inhabited with a population with famous purple colour from the Murex shellfish, this colour called 'Phoenix' in their language. Theophrastus may have derived the word 'Phoenix' and gave it to date palm fruits which appear purple on ripening (Bircher,1990)." [quoted from Alchemy in Islamic Times]
On Phoenix the bird there is a detailed history by Nigg, Phoenix: An Unnatural Biography of a Mythical Beast, who notes the influence of Lactantius's poem The Phoenix, and his alternative "etymology". According to him, contra Pliny, it is the tree, and Phoenicia itself, that was named after the bird, who weaved its nest on top of it:
"He is said to be the first to contend that the bird named Phoenicia
after itself. Then, à la Pliny, he points out that the bird and the date
palm share the same name, except that he says the tree was named for
the bird, the opposite of what Pliny suggested. While Aeolus impedes
the winds, Lactantius’s Phoenix, like Ovid’s, builds a nest of spices in
a tall date palm. The nest, similar to Ovid’s “crib” and “tomb,” is “cradle
or sepulcher — which you will— for she dies to live and yet begets herself.”"
Linnaeus refers to yet another late "etymology", by Kaempfer, who traveled Persia in 1680-s and left a treatise on the cultivation of date palm there, Phoenix Persicus. According to Kaempfer (see Schirg's Phoenix Going Bananas in Apotheosis of the North: The Swedish Appropriation of Classical Antiquity. p.32), the bird's name comes from a metaphor: the palm is the bird, the leaves are the wings, and the heat of Arabia is the fire, which "brings forth this wonderful plant and its nourishing fruit". Hence, "in reality it is the date palm, see Kæmpf", as Linnaeus writes of the Phoenix.
Babylonians and Assirians revered it as the Tree of Life. Popenoe gives more historical information on the tree and its cult in The Date-Palm in Antiquity (1924):
"It was emphatically a Tree of Life and is accordingly represented time after time on the monuments of Babylonia and Assyria... The palm cult, probably carried northward from Babylonia, found no lack of adherents among the Phoenicians and Syrians. It is frequently to be detected among the heathen gods to whom the Old Testament prophets animadvert... Phoenician traders had carried the cult to all parts of the Mediterranean as early as the Neolithic period. In graves of this age in Spain and Portugal clear evidence of it has been found.
That the Greeks obtained their knowledge of the palm from the same source is evident from the name they gave it - Phoenix, the tree of the Phoenicians. As the symbol of that country it is found figured on the Phoenician and, later, the Carthaginian coins struck in Sicily... It is not mentioned in the Iliad, but appears in the Odyssey, particularly in the well-known scene where the far-traveled Ulysses approaches Nausicaa on the strand and flatteringly beseeches her assistance... The palm near the temple of Phoebus in Delos, to which Ulysses refers, was one of the most famous in classical history: at clasping the trunk with her arms, Leta was fabled to have given birth to her son Apollo. The identical tree was shown to the credulous as late as the time of Cicero and Pliny, both of whom speak of it... By the beginning of the empire the date-palm is so well known that the elder Pliny is able to give an extended account of it, from Spain eastward to Persia..."