In Harry Potter universe, do Phoenixes have souls?
Canon based answers only please.
It seems clear from the Harry Potter books and films that animals (or at least certain animals) have souls and can become ghosts.
Members of the Headless hunt, for example ride on ghostly horses:
Through the dungeon wall burst a dozen ghost horses, each ridden by a headless horseman. The assembly clapped wildly; Harry started to clap too, but stopped quickly at the sight of Nick’s face. The horses galloped into the middle of the dance floor and halted, rearing and plunging; a large ghost at the front, whose bearded head was under his arm, blowing the horn, leapt down, lifted his head high in the air so he could see over the crowd (everyone laughed) and strode over to Nearly Headless Nick, squashing his head back onto his neck Chamber of Secrets
and Mopsy Fleabert has written an entire book about animal spirits.
Read more from Mopsy Fleabert about animal spirits and how to recognize them. Pottermore Wiki
Since becoming a ghost seems to be a function of having a soul in the first place, it seems likely that some if not all animals in the Potter universe have souls, Phoenixes included.