As to explain the evolution, as people have already commented, periodic fire is already present in nature, and often triggers seeds to grow, such as (I think) in proteas. Maybe the Phoenix have close mating pairs, the female of which sacrifices itself to start a fire, causing a reseeding of the area around, meaning many plants soon start to sprout, and the Phoenix chicks are fed by the father who catches the small mammals and other herbivores which gather to feed on the germinating plants. The reason the mother would be sacrificed would be because  she would already be low in body water and fat content from growing the eggs and so be the natural choice for being set alight. 
I think the main difficulty to overcome is figuring out a reason why the adult Phoenix would die from the burning, as this doesn't seem adaptive and so unlikely to be passed on.
This explanation would also skew the gender ratio as only the female Phoenixes would be dying this way so this would have to also be remedied by the males dying, or explained another way.

What I like better is on another track to explain the evolution of the burning, maybe it acts as a warning signal to other phoenixes, or better yet, or as a dis-incentive for predators. 
Maybe Phoenixes, like many kinds of butterfly, make themselves unpalatable to predators and do this by burning up when killed, stopping the predator from getting a meal, so causing them to stop preying on phoenixes, adaptive for hen as a group) This unlike some other explanations, would allow both genders of Phoenix to combust. Perhaps in this case, the Phoenix mythos of being reborn arose from parent Phoenixes being killed while nesting over their chicks/eggs which they would be vulnerable while doing. This would still be fairly adaptive as the remaining partner could still raise(at least some of) the chicks, and the predator that tried to attack them would surely learn it's lesson and not return. This would also not skew the gender ratio like the previous idea mentioned.

This ability could maybe be expanded once developed to allow Phoenixes to do things like:

Attract mates visually by flying up at night, catching a bit alight, before diving down to blow out the flame by the wind/rolling on the ground or diving in water. 
Cook their food (assuming they were carnivorous), thus freeing up gut space for digestion and allowing them to be lighter for their size, so allowing them to be larger/fly more efficiently.

The main problem would still be how the Phoenix manages to catch alight, but I think oily feathers are a good start- perhaps a mechanism like the bombardier beetle
Maybe modified salivary glands(which birds do have), contain chemicals which when mixed ignite, or maybe different types of feathers that in the rachis(stalk) contain different types of chemicals, so when pulled out, these mix and catch alight. This seems more on point with a Phoenix than the salivary glands as that is more getting into dragon territory, and this would also allow for Phoenixes, by pulling out a few feathers from different sides of their body (to prevent the two types of chemicals mixing on them so they themselves caught alight), to cook their food by placing them together on their prey so the liquids mixed and caught their uncooked meal alight. 

This of course would again need some explanation of how it arose. Possibly it started with proto-phoenixes, being quite intelligent, using natural sources of fire and eventually evolving to do it themselves?

Personally, I think this aspect of their evolution could be left a mystery, Phoenixes are, after all, magical/mythic creatures. So many things have actually evolved in nature we have no idea how to explain, that I think Phoenixes like this are plausible enough.