The phoenix would be, but the Horcrux would not
There doesn't seem to be any reason a phoenix couldn't be made into a Horcrux. We have precedent. We know Horcruxes can be made from living creatures, because Nagini was made into a Horcrux.
“I don't think so,” said Dumbledore. “I think I know what the sixth
Horcrux is. I wonder what you will say when I confess that I have been
curious for a while about the behavior of the snake, Nagini?”
snake?” said Harry, startled. “You can use animals as Horcruxes?”
“Well, it is inadvisable to do so,” said Dumbledore, “because to
confide a part of your soul to something that can think and move for
itself is obviously a very risky business. However, if my calculations
are correct, Voldemort was still at least one Horcrux short of his
goal of six when he entered your parents’ house with the intention of
—Harry Potter and the Half-Blood Prince
We should at least suspect that magical creatures can be made into Horcruxes. First, since there is no issue with turning highly magical artifacts into Horcruxes, even highly potent ones such as the Deathly Hallows.
Second, it seems possible that Nagini was some sort of magical creature before being turned into a Horcrux, since she had a venom that dissolved Mr. Weasley's bandages, and resisted even magical means of healing. Of course, it is possible that this is an enhancement of some sort that Voldemort applied to her.
'Well... well, I don't know whether you know what - what stitches
'It sounds as though you've been trying to sew your skin back
together,' said Mrs Weasley with a snort of mirthless laughter, 'but
even you, Arthur, wouldn't be that stupid —'
'I fancy a cup of tea, too,' said Harry, jumping to his feet.
Hermione, Ron and Ginny almost sprinted to the door with him. As it
swung closed behind them, they heard Mrs Weasley shriek, 'WHAT DO YOU
MEAN, THAT'S THE GENERAL IDEA?'
Typical Dad,' said Ginny, shaking her head as they set off up the
corridor. 'Stitches... I ask you...'
'Well, you know, they do work well on non-magical wounds,' said
Hermione fairly. 'I suppose something in that snake's venom dissolves
them or something. I wonder where the tearoom is?'
—Harry Potter and the Order of the Phoenix
However, though a phoenix probably could be transformed into a Horcrux, it would make a terrible Horcrux, precisely due to its powers of regeneration. We know when a living Horcrux is killed, the piece of soul within it is destroyed, as happened with Nagini.
We also know that it is possible for a Horcrux (or something close enough, in any case), to be subject to an otherwise lethal event and to survive it. In that case, it appears that the piece of soul within is destroyed, whereas the vessel will survive unharmed. This happened to Harry Potter, for example:
“So the part of his soul that was in me . . . ”
Dumbledore nodded still more enthusiastically, urging Harry onward, a
broad smile of encouragement on his face. “. . . has it gone?”
“Oh yes!” said Dumbledore. “Yes, he destroyed it. Your soul is whole,
and completely your own, Harry.” “But then . . . ” Harry glanced over
his shoulder to where the small, maimed creature trembled under the
“What is that, Professor?”
“Something that is beyond either of our help,” said Dumbledore.
“But if Voldemort used the Killing Curse,” Harry started again “and
nobody died for me this time —how can I be alive?”
—Harry Potter and the Deathly Hallows
He could not die, since his mother's enchantment in Lord Voldemort's body tied him to life. So when he was hit with the Avada Kedavra curse, it destroyed the portion of soul within him, and cast him to the antechamber to the afterlife, whence he returned to life.
A phoenix resurrects when it dies, even when it dies of natural causes:
“Fawkes is a phoenix, Harry. Phoenixes burst into flame when it is
time for them to die and are reborn from the ashes. Watch him . . .”
—Harry Potter and the Chamber of Secrets
Thus, if a phoenix were killed, or indeed likely died of old age, the soul fragment therein would likely be destroyed, while the Phoenix would resurrect in the usual manner. Indeed, given the usual proclivities of phoenixes, it seems likely that they would attempt to hasten this process. You don't want to entrust your soul to a being as noble and self-sacrificial as a phoenix:
Fawkes swooped down in front of Dumbledore, opened his beak wide, and
swallowed the jet of green light whole. He burst into flame and fell
to the floor, small, wrinkled, and flightless.
—Harry Potter and the Order of the Phoenix
A phoenix could probably be a Horcrux.
However, given that the Horcrux would be rendered useless when the phoenix regenerated, and that a phoenix wouldn't be likely to want to be a Horcrux anyway, making a phoenix into a Horcrux would be a poor choice.