Very belated answer, but stumbled upon this and came up with a viable solution I liked enough to be worth suggesting. I think this can be done realistically!
The short version is that when a female dies if she is carrying an egg the egg is encouraged to hatch, though she can have young with regular laying of eggs as well.
I'll try to go through the evolutionary steps as I did with my gryphon example. Were start with a 'normal' bird as our basis.
When in doubt set things on fire
First we have to explain how gryphons got associated with fire to begin with. I think this could work as an evolved defensive techniques. Pheonix aren't always on fire, but they can trigger 'fire' to scare off attacking predators.
Most wild animals have a huge ingrained fear of fire and flame. As such it would actually be a potentially good survival tactic to use flame to drive them away. I'm not necessarily suggesting using it to set something on fire, you don't need anything too drastic to scare someone away. Even if she could only create a short duration 'spark', something bright and scary but not burning dangerously hot or controlled enough to do serious harm, this could be still be a viable defense. Even if the predator isn't driven away by the sudden flame the bright flare could throw off it's vision, blinding it enough for the pheonix to escape.
I imagine original flavor pheonix only carred enough to make a few sparks right when a predator was chasing her. Once she discovers the usefulness of scaring away predators she could then evolve to realy on the flame more extensively for defense, but for now let's focus on the first limited use of flames while flying, I'll get to how the practice evolved after that.
Of course fire requires lots of energy to produce. The high energy expense of fire means that it would litteraly burn through calories if the phenoix was requierd to produce the flames herself, to the point she could starve to death from excessive caloric cost of constant flames. More importantly, it's nearly impossible pheonix's evolving a way to create and control any fire-producing chemical entirely on her own, there aren't any safe 'intermediate' steps where it's beneficial to have a means of producing an explosive chemical before it's been evolved to be part of pheonix defense.
That's okay, there is an easy solution here. The pheonix doesn't produce the fire, she steals it. I think she could find a natrually existing substance in her habitat that is flamable, which she collects and later uses to produce her flames. There are actually two possible approaches here, so I'll mention both options below, but in both cases I'm going to call this substance 'Exo' (for exothermic reaction), just to have a covenient term for it.
The important part here is that she must collect this substance, she can't produce it entirely on her own. Just like birds collect food and water the Pheonix would likely hunt for and collect Exo. If she runs out of Exo she can't defend herself well, and thus as her Exo reserves run low she will actively hunt it from her habitat.
Here are the two options I see for the origin of Exo and how she first tarted using it.
1. Fire Water
First option is that Exo is a chemical, likely a liquid, which can be triggered to start an exothermic reaction. She would need something that wasn't too flamable, that wouldn't explode into flame when not desired and kill her. Thus she would be looking for something relatively stable, but which can be triggered to start an exothermic reaction quickly as well, likely by mixing it with a catalyst chemical to start the reaction. Best case would be that she already naturally produced a chemical that acted as a proper catalyst and 'accidentally' discovered she could exploit this to trigger the Exo.
In terms of natural chemicals she might produce I would say most likely it would be her urine that happened to contain high concentrations of some chemical that servied as a catalyst for the Exo. The trigger being waste makes most sense to me, as it's the one place likely to have a high concentration of many different potential catalystic chemicals, and the safest place for chemicals that could be harmful to the body to end up (I imagine the catalyst is unlikely to be something good for the Pheonix). For that matter it makes sense that a Pheonix would discover the ability to trigger Exo as a defensive mechanism this way, as many species will expell waste when in fear, discovering that the dropped waste then set off some natural deposit of Exo on the ground to drove off her predator is a sensible 'first step' to start evolving a more intentional use of Exo for defense.
the 'fire water' approach with urine trigger would be by far best case for having a realistic evoluiton, if the appropriate chemicals exist in real life. The key catch is that I'm hand waving the existance of Exo chemical in nature due to my lack of chemistry knowledge. I can't point you to a specific chemical that has this sort of exothermic property, though I suspect someone could suggest some (if someone wants to add a comment about good options I'd be happy to add them and give credit!).
To help justify her being able to trigger Exo to flame perhaps the original the Pheonix didn't carry this substance around, but it was common enough to be useful for defense if she was close to a patch of it alread, with her discovering it as I mentioned above by accidentally triggering these natural Exo deposits when fleeing. This first triggered reaction may have been very small compared to later Phenoix could do, but still enough to provide a distraction and thus an evolutionary advantage.
Her ability to trigger larger, and more controlled, exothermic reaction in 'present day' may have evolved from this defensive method, with there being enough natural Exo deposits that gryphons better able to exploit them for defense lived longer and made more hatchlings. Only after she reached a certain degree of 'skill' at triggering Exo did she switch to carrying it around for a more mobile defensive method.
Once the pheonix was use to using Exo on the ground she started to carry a small amount of exo with her when she flew, so she could set it off in the air to drive away attackers when no natural Exo deposits were nearby. I imagine first 'draft' was exo getting on a pheonix claws while the phenoix walked around an Exo deposit, then when the phenoix was flying later the exo on her claws could be ignited later. If Exo doesn't burn too hot maybe she set off the Exo sticking to her claws and let her claws burn even though it singed her slightly just to scare off attackers.
Once the first arial use of Exo started the pheonix would naturally evolve to be better at it. Storing larger amounts of exo in specialized Exo storage organs, being better able to dispel it and the Trigger for it. All kind of more sophesticated controled use of Exo to create flame, Once you get over the first hurdle of using it in the air at all Evolution will do the rest.
One key detail, this substance would likely need to be something that she can't eat. It could be toxic or just not easily digested, but it's not something she can draw energy from directly, it's only useful to her as a source of fire.
2. Silent but Deadily: gassy doom
The other option is that Exo takes the form of a lighter then air (LTA) natural gas, which happens to to naturally leak into the air from vents in her habitat (likely a volcanic one in this case?).
On the down side these sort of natural gases tend to be more explosive, and thus more dangerous for a pheonix to carry around. On the plus side there are many known LTA exothermic gases, so unlike with the last example we don't have to handwave a naturally occuring exothermic chemical existing.
The question is why a pheonix would interact with such gases despit the risk of an explosion hurting her. I have a good potential answer though, boyancy. Perhaps a pheonix is heavier then normal birds (particulalry when pregnant, see below), and thus needs some help with the flying. A pheonix may have evolved to use LTA gases from vents to fill up some sort of air bladder to help offset her weight when flying. Even if the natural gas was slightly dangerous it could be worth it for the non-trivial caloric savings of not wasing as much energy on flight and the ability to lift larger weights when flying.
So originally the Pheonix would collect gasses for boyancy only, refilling her 'bladders' with gas when she needed to increase her boyance. The original gas bladders likely weren't filled entirely with Exo, since Exo would be too dangerous a gas to evolve to use for lift at this time and because most natural gases would be a combination of gases anyways. She likely filled her bladders at natural vents containing many LTA gasses, with Exo being only one of the gases, and possibly present in small enough quantities to not be overly dangerous.
As part of using gas to control he boyance the Pheonix would evolve to expell gas rapidly, to allow for rapid dives. When under attack by something diving at her expelling her bladders to help her to dive out of the way would be a naturally evolved tactic.
At some point the Pheonix 'discovered' that when she expells Exo from her bladder she can set it off to create a flame in the air to scare/disorient persuers. This could be a random mutation that made her better at setting the Exo off. Perhaps the pheonix evolved stronger muscles to excelerate dumping her bladder until she was able to exert enough pressure that it triggered Exo, or perhaps we go back to the idea of urine having a catalizing reaction and the pheonix evolved to dispel urine along with bladder gas to trigger the explosion. Alternatively perhaps, by chance or evolutionary pressure, the pheonix moved towards using gas vents to refill her bladder that had higher Exo concentration causing her bladders to now have enough Exo to trigger a reaction.
Whichever process happened originally the Exo would likely not have been a very spectacular reaction, a very minor spark that didn't burn very bright. However, if it did enough to even temporarily distract or confuse her attacker it would be enough. From there evolution would encourage better use of Exo.
First the Pheonix would become better at triggering the exo reaction, using whichever of the above methods she used to set off the exo, or developing a new method if the first uses of Exo were unreliable due to Exo not flaming reliably enough. She would also develop better means of using Exo to get away, aiming the Exo towards her persuer before igniting it or being able to ignite it from multuple points of her body instead of just the one bladder exaust point.
After that the Pheonix would become better at collecting Exo over normal natural gases. This would mean either explicitly hunting out vents with higher Exo concentration, or possibly a filtering method where she would fill her bladders with normal LTA gases, then filter out non-Exo gases and refill, slowly building up a reserve of Exo by expelling non-Exo.
Your flashy tricks won't protect you forever
The problem with using a defensive mechanism that primarily relies on scaring/surprising predators (not actually harming them) is eventually your predators get wise to your tricks. Those that you scare away don't catch a meal and risk starving, and eventually only those predators that aren't afraid of your tiny tricks will live on to spread their genetics. Your going to have to esculate your defenses accordingly.
So while Exo may start as a distraction the Pheonix will likely double down on it. Developing ability to carry and use larger quantities of it, to burn it hotter or keep the burn for longer, to aim it towards attackers and/or disperse flame over a larger region. I suspect their biggest focus though would be to burn it brighter, which may not be hotter, since even if predators aren't afraid of the flame your still mess with their vision by tossing such a bright flame behind you (and predators will never evolve to be as good at filtering out bright flame from their vision as you because you know exactly when to expect it and they have competing evolutionary pressures limiting their ability to specialize in hunting you).
The important part of this is that Pheonix will be carrying far more Exo, and fuel to ignite it, on them.
You predators think I'll be an easy meal? Well I say Bite Me!
Eventually all this flammable substance will come back to bite the pheonix as occasonally she will set herself on fire when she fails to prevent a reaction on occasions. But more importantly, it will come back to bite predators when a predator tearing into her body accidentally sets off the Exo in her body and has their meal explode in their face.
This would originally be an 'accident', the Pheonix carries lots of explosives in her body and she doesn't care if it explodes after death so evolution hasn't done anything to prevent that. However, evolution loves the old addage "it's not a bug, it's a feature". Given time I suspect the Phoenix will actually evolve to intentionally explode when fatally wounded.
Their reason for this is similar to the reason that many reptiles waste energy producing dangerous poisions and then paint themselves bright red and taunt predators to eat them. Predators don't want a meal that's going to hurt them, and one that blows up in your face counts as that. The pheonix will find that having their last move be to harm whoever killed them is a very effective method to discourage attackers from hurting them.
To make this even more effective let's presume Pheonix as pair mating and caring for their young Now a mother (or even more so daddy) pheonix has more motivation for being able to die explosively, to hurt predators that are hunting close to their nest, and to discourage predators from attacking their mate and children in that nest.
Thus we finally know why pheonix ignite into flames on death. It's done to hurt their predators and to consume all the meat of their body so that even if a predator isn't harmed he still won't get much of an edible meal from the hunt. It discourages predation, and besides which it's a natural result of the pheonix body no longer regulating the explosive chemicals contained within. Pheonix likely will be able to do this as a concious decision at any time, as part of protecting their nest/mate/young, but in addition it likely will happen naturally at death or fatal wounding.
Other species fire babysitters for doing that you know
(look, two puns in one title, I'm getting punnier!!)
Once a pheonix starts carrying and using Exo they will likely find other uses for it, evolution is pretty good at reusing designs. I imagine they will likely be used longer distance communication (setting off flare-signals at night) or attracting mates with fire dances etc. Most importantly for now though they likely will be used for hatching eggs.
Keeping an egg warm is important to hatching it, thus the reason birds sit on their eggs. However, Pheonix mommies carry around a portable heating source they have unique mastery of, seems kind of silly not to use it to avoid all that boring egg-sitting time.
I imagine that the Pheonix would do it's best to find ways to Exo to help with tihs process. In the case of Exo gas perhaps they will regularly expell a very small quantity of exo and ignite it, since low quantity exo will only produce a little exta heat but not enough to burn the egg. For the 'fire water' exo they may paint small amounts of it on the egg before ignighting it, or create some mix of Exo and something non flamable to cover the egg before lighting it, perhaps even leaving a small Exo-mix 'burning' at a low temperature over the egg while they leave to hunt, depends allot on what the Exo chemical is.
This would free the Pheonix up to do more travel and hunting, and thus potentially to care for more eggs, potentially. But for now the reason this is relevant is mostly that the egg will already be evolved to handle slightly higher heat then most bird eggs, and to gain more of a speed increase in rate of growth when near heat.
Daddy says my mom was Hot Stuff before I was born
Now we get back to the whole pheonix reborn subject, which I kind of already suggested in the intro. Imagine a pheonix mother who is already carrying an Egg at the time that she is fatally wounded. She wants that unborn egg to still survive if possible. She will want to evolve a method of encouraging the egg to finish it's growth and hatch even without her support. This sort of thing is seen in other creatures, most mammals when badly wounded will go into labor and attempt to give birth in hopes that the child will survive even if the mother dies for example.
So imagine, long after immolation pheonix became common, a seperate evolutionary process lead to encouraging the pheonix eggs within the mother to still survive.
Originally this would simply mean the mother evolving to protect her egg from burning up in immolation, by igniting the outside of the mother's body but keeping the egg away from the hotest parts of the flame and evolving an egg shell that is good insolation against short duration, high heat, burns. Alternatively maybe the mother simply becomes good at expelling the egg on death, by laying it or other means, so it stays away from the main flame of the mother.
Later this could change to the egg actually triggering an alternative growth pattern when it sense enough heat to suggest immolation. This could be the egg switching to hatching earlier, when the bird isn't fully formed yet, to allow a chance of the hatchling finding safety, or the egg switching to a slower growth approach that doesn't require as much heat so the egg has a chance of growing to 'term' even without a mother incubating it.
If pheonixes raise eggs as a pair the mother may even have an approach of burning in a way that helps the father find and cary the egg away from danger back to the nest after the mother dies. This seems the most evolutionarily sound option, but also the least similar to 'pheonix reborn' myth.
Pregnancy means discussing getting fat and that good old 'bloated' feeling
Part of the problem with these solutions is that any egg that hasn't been hatched yet is likely far enough away from hatching that none of these give any reasonable chance for the baby to survive to hatching, much less survive to adulthood and have children of it's own. However, if you go with the gas-Exo approach this becomes slightly more forgiveable.
The problem with laying eggs is that their vulnerable. When you leave your nest your risk someone coming along and eating your children, their hard to protect. And since you have to incubate them you still end up spending most of your time stuck with them. Mammals realized this and decided if their going to keep taking care of the kids that long they might as well keep the kids inside the womb and let them grow there, at least thta way you can carry the kids around with you when you have to move.
Birds can't do this though, because of weight constraints. Birds have to fight hard to stay in the air, they've evolved a million ways to keep their weight low so they never get too heavy to be able to fly. Being pregnant would be difficult for this reason, the added weight, and lowered aerodynamic structure, of a full term child would make it hard for the mother to keep flying...usually.
However, a pheonix that exploits LTA gases to stay afloat doesn't need to worry about this as much. She can simply fill her bladders with more gas to counteract the weight of the egg. Sure she won't be able to fly as nimbly this way, but the again she doesn't need to be as nimble if she has scared off most predators with the threat of exploding in their faces.
The end result is a gas-pheonix is a bird that actually can afford to carry it's children to term! This includes allowing the children to grow larger then a newly hatched bird is, to be closer to self sufficent at the time of hatching.
Consideing this it's not unreasonable to imagine gas-pheonix carrying the egg within themselves for most of the pregnancy instead of having traditional nests. They may lay the egg only when it's intended to hatch and have the baby hatch as soon as the egg is layed (possibly with mother helping to break the egg?) This means when a mother bird dies it's possible for the egg it's carrying to be close to full term and ready to hatch into a larger-then-normal-hatchling size baby pheonix that actually stands a (small) chance of surviving on it's own without it's mother. Thus the gas-pheonix is the only one that seems reasonable to benefit from trying to protect an unlaid egg, as the only version where that egg may be large enough and developed enough to stand a chance of surviving.
A Womb with a view, and a heater
The most pheonix like option is probably the biggest handwave, but isn't necessarily impossible. That's having the mother switch to a 'slow burn' death. When the mother is carrying an egg and dying instead of the usual immulation, or possible in addition to it, she dies in a way to allow a slower burning of Exo within her corpse. The idea being that the Exo burns slowly enough that the mother's corpse becomes an incubation chamber for the egg, a way to keep the egg warm for a longer period of time so it has enough time to grow and hatch properly.
This version is harder, as it requires such percision in death and Exo 'burning' that it streatches credibility that it could evolve through unguided evolution. Still, it's a very cool idea that I may forgive some handwaving.
These kids will be the death of me
As an alternative to the above there is a slightly more realistic evolutionary option, that mother changes to Exo incubation mode when badly wounded, but not yet dead! When a mother is badly wounded, or very old, or otherwise at the state where she doesn't expect to survive much longer she may decide to focus on making sure this one last egg hatches before her death, even if it means sacrificing any chance of survival after the hatching to focus all her remaining energy on the child.
So she settles down somewhere to well...die. She slowly starves herself over the next week or two, not bothering to eat, while burning her remaining exo inside herself to excelerate the egg's incubation with the extra heat. If a predator sees the wounded pheonix they will be hesitant to attack it since the mother could still immolate itself to kill/wound the predator if attacked, so the phonix is left alone to slowly die while incubating it's last child.
It could be that in this wounded/starved state the mother isn't able to go through a hatching once the egg is ready to hatch due to how week she is, or even that the hatchling is triggered to grow to a larger state before hatching when the mother does this to give it the best chance of surviving on it's own after hatching. In any case the mother is unable to give birth to her final hatching and so immulates herself when the egg is ready to hatch as the final step. to let the egg hatch.
Perhaps in this version the hatchling hatches inside the mother and the birth of the hatchling can trigger the final immolation by messing with the mother's Exo bladders when it's hatching? Alternatively the mother doesn't actually immulate until right after the hatchling hatches (and is far enough away to not be burned), but to passing humans it looks like the hatchling is coming from the immulated corpse rather then the hatchling hatching and then the corpse immulating right after?
To go even more morose perhaps the hatching can hatch and eat the mother from the inside if it's still alive for more energy to grow, so it's bigger and stronger before it's on it's own, whlie depending on the threat of the mother 'exploding' if a predator tries to eat the dying mother to keep it safe.
The approach of having the mother still alive, and just committing to protecting it's final hatchling, works better then the mother's dying and egg surviving on it's own because it means the mother is able to buy the egg some more time to grow, increasing the chance that the egg will be in a healthy state to hatch. It's also more believeable that many itterative adaptations can push the mother towards being very good at protecting her last egg compared to the above proach of the mother somehow dying in such a way that she makes a incubating corpse for the child. Here it could start with mother's simply committing more energy to caring for a child when injured and mother slowly upping the amount of sacrifice she can make for her last chlid to increase the odds of one last hatchling being born.
** I don't have any Eggcelent puns for this one**
The one minor question that comes up is why people think all pheonix are reborn this way if only a small subset are (those who's mother's are carrying an egg at time of injury/death and who survive to hatch afterwards).
Mostly I'm just going to say human nature, they see some hatchlings reborn from pheonix and so assume thta's how all pheonix are and that the times they don't see a pheonix being 'reborn' are simply because they didn't wait long enough for the rebirth (or that phenoix can only be rebirn sometimes and some deaths are final).
Still, there are a few things you can do to further this belief. One is to make sure mother's are always carrying eggs, which isn't too hard. Many species tend to mate when they can find a male, even if that isn't when their ready to bear young. Kangaroos are the first species to come to mind to me (and really, many marsupiles), but their by no means the only type. They usually do this because their not certain to have males available when they are ready to carry and have young.
So if you want to increase mother's trying for a final egg just say that mating and child rearing times of the year are different. Perhaps Pheonix mother's only mate during migration when males and females come together, but after conceiving the pheonix mother will fly away and only much later will she decide to trigger growth of the egg to give birth during warmer seasons when the young will be better prepaired (or maybe even during seasons when Exo is easier to find?).
This implies only one young a year being born, which implies Pheonix have long lives and generally care for hatchlings for some time. If Pheonix have few predators, due to their immolation defense, this could explain their longer then usual lifespan, and gas-pheonix may act like albatross and tend to migrate over long distance, even oceans, justifying a larger size and thus shorter birth rate.
Since pheonix have fewer predators it also increases the odds of a mother living to 'old age'. Thus increase the odds that a mother will reach the point where she is old enough to be unable to have many more young and chooses to go the final immulation route to ensure her final egg makes it despite her failing health.
No dad's allowed
There's also the problem that half of pheonixes are male, which means at most half of phoenixes that die could be incubating a final egg. You could have males look different and thus not usually be considered 'phonix' so that the myth only applies to the female pheonixes. Perhaps females use far more Exo, due to their need to increased lift to counteract the weight of large & heavy eggs, and as such their larger and more prone to using fire as a defense and thus are the only ones that are noticed.
Alternatively if you say that females only mate during migratoin season, as mentioned above, you could always say that females prefer to frequent different habitats then males and that the areas with pheonix-reborn myths tend to be habitats that are more attractive to females (again likely those where Vox is more plentiful for gas-pheonix version at least).
and...this answer was again way to long. But hopefully you like the idea :)