Orcs appear to be sentient. Orcs are (possibly) derived from elves who do possess fëa. So do they possess "a soul"? and if so, what happens to it when they die? do they get the gift of men?
The following quote (emphasis mine) from an essay on Orcs in Morgoth's Ring, volume X of History of Middle-Earth, settles this question:
The least could have been primitive (and much more powerful and perilous) Orcs; but by practising when embodied procreation they would (cf. Melian) [become] more and more earthbound, unable to return to spirit-state (even demon-form), until released by death (killing), and they would dwindle in force. When released they would, of course, like Sauron, be 'damned': i.e. reduced to impotence, infinitely recessive: still hating but unable more and more to make it effective physically (or would not a very dwindled dead Orc-state be a poltergeist?).
But again - would Eru provide fëar for such creatures? For the Eagles etc. perhaps. But not for Orcs.
It does however seem best to view Melkor's corrupting power as always starting, at least, in the moral or theological level. Any creature that took him for Lord (and especially those who blasphemously called him Father or Creator) became soon corrupted in all parts of its being, the fëa dragging down the hröa in its descent into Morgothism: hate and destruction. As for Elves being 'immortal': they in fact only had enormously long lives, and were themselves physically 'wearing out', and suffering a slow progressive weakening of their bodies.
In fact, your presumption that "Orcs appear to be sentient" is incorrect: it seems that orcs were not even considered sentient beings, but rather dumb beasts in humanoid form who could talk in a manner akin to parrots. Quoting the next paragraph from the same essay (again, emphasis mine):
In summary: I think it must be assumed that 'talking' is not necessarily the sign of the possession of a 'rational soul' or fëa. The Orcs were beasts of humanized shape (to mock Men and Elves) deliberately perverted I converted into a more close resemblance to Men. Their 'talking' was really reeling off 'records' set in them by Melkor. Even their rebellious critical words - he knew about them. Melkor taught them speech and as they bred they inherited this; and they had just as much independence as have, say, dogs or horses of their human masters. This talking was largely echoic (cf. parrots). In The Lord of the Rings Sauron is said to have devised a language for them.
The following quote from the Tale of Adanel (emphasis mine) shows that even choosing to serve Melkor greatly reduces one's fëa almost to destruction. So it makes sense that orcs, who were created as servants of Sauron and thereby Melkor, would have no fëa to begin with:
Some Men say that he blasphemed Eru, and denied His existence, or His power, and that our fathers assented, and took Melkor to be a Lord and God ; and that thereby our Fëar (Soul) denied their own true nature, and so became darkened and weakened almost to the death. And through the the weakness of the Fëar our Hroar (Body / Matter) fell into unhealth, and lay open to all evils and disorders of the world. And others say that Eru himself spoke in wrath saying: If the darkness be your God, little here shall you have of Light, but shall live it soon and come before Me, to learn who lies, Melkor or I who made him.