"That soul shall be cut off from the midst of its people" — the Mekhilta asks what this verse adds to "those who profane it shall be put to death," which has already been stated. Both seem to describe the same consequence: death for violating the Sabbath.
The answer lies in the difference between two types of Sabbath violators. "Those who profane it shall be put to death" addresses someone who violates the Sabbath willfully, after having been formally warned by witnesses. This person faces judicial execution — death at the hands of a human court.
"That soul shall be cut off" addresses a different case: someone who violates the Sabbath deliberately but without the formal warning from witnesses that would make him liable to a court. He acted willfully — it was not an accident — but the procedural requirements for judicial execution were not met.
This person faces kareth — being "cut off." This is a divine punishment, not a human one. His soul is severed from the people through an act of heavenly justice. No court pronounces the sentence. God executes it directly.
The two verses together create a complete system. With witnesses and warning: human court, death penalty. Without witnesses and warning, but still deliberate: divine punishment, kareth. The Sabbath violator faces consequences either way. The absence of witnesses does not create impunity — it merely shifts the jurisdiction from the human court to the heavenly one.