In "The Goose Girl", the villainess is asked what is the appropriate punishment for her crime, before she knows her evil deeds have been uncovered. When she says, "She deserves to be put stark naked into a barrel lined with sharp nails, which should be dragged by two white horses up and down the street till she is dead." the sentence is carried out.
In "The Death of Koshchei the Deathless", Koshchei chops the hero into little pieces, throws them into a barrel, and throws the barrel into the sea. (His brothers-in-law revive him, though.) When time comes for him to kill Koshchei, his horse cracks Koshchei's skull, and the prince finishes him off with a club; then he burns the body and scatters the ashes.
In this case, though, the excessive death as a way of showing that Koshchie was really Killed Off for Real is justified, given that both Koshchie and the hero have proven quite capable of coming back from anything less.
In "Faithful John", the king is thinking to execute Faithful John because of his apparently absurd behavior. John explains and falls under the curse — he is turned to stone. Then the king and queen learn they can restore him by killing their twin children and using the blood. (However, after they have done so, the revived Faithful John restores their children to life.)
In "Ferdinand the Faithful", at the end, the queen likes Ferdinard better than her husband. So she declares she can cut off people's heads and restore them; the king makes her try it on Ferdinard, and then she cuts off his — but then says something went wrong, so she can't put it back on, and marries Ferdinard instead.
In "The Singing Bone", the younger brother is murdered by the envious older. His corpse rots, someone retrieves a bone from it and makes a flute, and the flute begins to sing of the murder.
In "The Robber Bridegroom", the heroine hides in the robbers' lair and sees them tear a captive woman to pieces.
In "Frau Trude", the little girl goes to a witch's house, where the witch turns her into a block of wood and burns her.
In "Fitcher's Bird", Fitcher has a room where he keeps bodies he has hewn apart. Two sisters end up dead there, but the third rescues them, and then Fitcher and his friends are burned to death in the house.
In "The Juniper Tree", the Wicked Stepmother closes a heavy chest on the stepson's head, killing him. She then sets up her own daughter to think that she had killed him, and disposed of the body by cooking it and feeding it to the father. When the boy comes back as a bird, he drops a millstone on the stepmother's head, killing her.
In "The Three Citrons", a slave murders the heroine with a hairpin. When she returns as a dove, she has her killed and cooked. When she returns a third time, the king asks what sentence would be suitable for someone who harmed her, and the slave prescribes burning, and the ashes being thrown from the palace roof; so she is.
In "The Wonderful Birch", a Wicked Witch turns the heroine's mother into a sheep and by shapeshifting takes her place; she has the sheep killed and feeds it to the woman's husband, although the daughter does not eat and manages to bury the bones.
In "The Twelve Brothers", after the king's Wicked Stepmother had his wife framed for witchcraft but her brothers saved her, the stepmother was "put into a barrel filled with boiling oil and venomous snakes, and died an evil death."
Another Russian folktale has Baba Yaga fall off the magical bridge of bones which she conjured up and falling either into a Bottomless Pit or a deep river, in which she drowns.
In "Biancabella and the Snake", Biancabella has her eyes and hands cut off and goes through quite the Break the Cutie process. With the help of her "sister", the shapeshifting snake Samaritana, they return home in disguise (after Biancabella gets better) and trick the Wicked Stepmother that caused Biancabella's misfortune into declaring that a criminal should be thrown into a hot furnace. The girls reveal the treachery and the stepmother and her daughters and henchwomen are the ones thrown into one instead.
Mr Fox works his way through a few wives until Lady Mary presents evidence of his crimes to her male friends. A musical version by the 1960s electric folk band Mr Fox bowdlerised the story slightly by showing only one incident where Foxy chops off the hand of a young girl and having him torn to pieces by dogs, but this English folk tale is not found in many modern collections of stories...