Did you try simply looking in a dictionary? For example, on dictionary.com, the etymology listed for "phoenix" reads:
before 900; < Latin < Greek phoînix a mythical bird, purple-red color, Phoenician, date palm; replacing Middle English, Old English fēnix < Medieval Latin; Latin as above
The Wikipedia article for Phoenix also draws a clear etymological line:
In Greek mythology, Phoenix (Greek: Φοῖνιξ Phoinix, gen.: Φοίνικος), the eponym of Phoenicia, was a son of Agenor and Telephassa (or Argiope), brother of Cadmus, Cilix and Europa.
When Europa was carried off by Zeus, her three brothers were sent out by Agenor to find her, but the search was unsuccessful. Phoenix eventually settled in a country in Africa which he named Phoenicia after himself.
Did an ancient mythological bird and son of a goddess really name Phoenicia? No, but then neither did a pair of mythological twins who suckled from the teat of their mother wolf found Rome. Nevertheless, that's the mythological etymology. It's a bit of which came first, the chicken or the egg? Did the real world name get created out of the myth? Or did the mythological etymology come out of the name? In both of these ancient instances, we may, and probably will, never know.