When I add additional hit dice to an undead monster and its size increases, should I increase its Charisma in place of its Constitution score?
For example, let's say I'm advancing a Wraith to 16HD to create a Dread Wraith. Should I increase its Charisma score by +4 (as I would do the with the Constitution of an animal that went from medium to large) or leave it at 21?
There is no rule that says you increase Charisma in the place of Constitution for size increases for undead creatures.
However, as the DM, you may feel free to increase the creature's Charisma to your heart's content to bring it up to a challenging level for you player characters.