Simply put, in current terms this has happened in a few super hero/science fiction moveis and TV, shows such as Highlander, Torchwood, Deadpool 2 etc. and its ruling seems to vary dependent on plot.
In Torchwood, after the immortal character, Captain Jack Harkness, is blown up, he regrew from whichever part was the largest. So in a beheading situation that would be the body, if all limbs and head were removed it would still be the torso as the largest part. this is fine for the show as its not that deep on the science part of science fiction, but my issue is how does the charactter, once regrown, have any memories? if the brain regrew then it should be a blank slate
Then there are cases such as Deadpool, where the head regrows a body, this is fine from a memory stand point, but then where does the base mateiral and organs to convert and use that material come from?
I think Highlander did it best, the only way to kill an immortal is to remove the head, any other damage won't kill and can be healed/regrown, chop off the head and the "immortal" dies and his power is given to the executioner.