The question of "should this character's alignment change?" is always difficult to answer, and we can't really answer it here. (I'd argue that, if the characters don't particularly want to perform the evil act, but it's their only way to survive, that should be less likely to mean it's an alignment change.)
But "is this particular act an evil act, such as would cause a paladin to Fall?" is an easier question. Making deals with evil creatures is pretty evil, and trading in souls is definitely evil. If your paladin goes along with this, I think he's in trouble.
-- and, by the way, this is the sort of trouble that should be clearly telegraphed. If the paladin goes to extract the giant's soul, he should be able to feel that what he's doing is deeply evil and is going to put his paladin status at risk. For a bad consequence of this magnitude, you should make sure that the paladin doesn't stumble into it by accident.
But I think the question you're really asking is something different. You're asking: "hey, isn't this kind of awful for the paladin, to be put in a spot where he has to lose his paladin status to survive? As the DM, should I really be doing this?"
The answer is: yes, that's pretty awful, and no, you shouldn't be doing this. Your paladin will try to find a solution to this problem that doesn't involve committing an evil act and losing his paladin status. Maybe he'll try intimidating the hag into giving the group the answer anyway; maybe he'll try bargaining and offering something other than a soul; maybe the group will attack the hag. Heck, maybe he'll pray for divine guidance.
Whatever the paladin does, you should try very hard to let it work -- ie, try to let him find a solution that will let the party escape without violating his code of conduct.