Fire Emblem has perma-death, but it's a Tactical RPG where you can recruit several dozens of unique characters. It's not really hard, but many players choose to restart the map whenever they lose someone. Playing through the whole game without losing anyone can be pretty hard.
Perma-death in RPGs is probably harder for the developer than the gamer, both in terms of balancing and storytelling.
If the player loses units towards the end of the game, they can just replace those units with one of their many reserve units. However, those reserve units may not have the necessary experience to be useful. And if the player loses units at the beginning of the game, they won't have any replacement units to use, which would make the early game much harder.
From a storytelling perspective, you'll need to explain why your characters are doing what they're doing. If Alice wanted to defeat the Demon Lord, and Bob decided to tag along because Alice is an interesting person, then if Alice were to die, why would Bob continue the quest to defeat the Demon Lord? And if Bob died as well, why would Charlie take over? What if Alice needs the Master Sword to defeat the Demon Lord, only Bob can acquire it, but he dies?
Of course, you could solve this problem the way Xcom does: by removing all important characters from combat, and making all combatants randomly generated units. Or you could do it the way Fire Emblem does: by limiting the secondary characters' impact on the main story branch, and showing the Game Over screen whenever an essential character dies.
As a result, perma-death leads to the following problems:
- A shallow cast of protagonist, where nobody has any real impact on the story.
- To avoid a shallow cast will require a massive amount of planning effort for the story to still make sense, no matter who dies and when.
- Lots of characters to replace those who die (have fun creating all the sprites, or implementing a system to procedurally creating them).
- Procedurally generated characters inevitably leads to a shallow cast.
- More demanding balancing to ensure the game isn't too easy or difficult at the beginning or end.
- This includes keeping the party balance in mind. What if the player loses all their healers?
- Limited possibilities in terms of gameplay. What if the only Pokémon that can learn "Strength" dies? How will the player push boulders and progress?
- Save scumming. Many players will simply reload their previous save over and over again until everyone survives.
When designing a game with perma-death, you should always assume that all characters who can die have died, and design your game accordingly.