When you find the Phoenix follow it around till the heatwave ends. You can build a taming box around the ashes and when it wakes up it'll be an easy tame. Flamethrower seems to work better than flame arrows and I'm assuming the fire wyvern works best of all but I haven't tried it with mine yet.

More Phoenix Taming & KO Tips