I debated between mana cost, discard a card cost, or both.

Or even "put on top of your library", like dredge but only when it dies, not any time from your graveyard.

Probably too repetitive to be a good mechanic.

It's not any more repetitive than regeneration. In fact if it was a triggered ability rather than a static ability defining a replacement effect, it would be on of the current keyword mechanics I have queued up for playtest.

p.s.: I'm a little surprised by the choice of color - this clearly seems like some variant on self-bounce/regeneration. Wouldn't have put this in red (Uthden Troll?).

Oh yeah. I was looking for a "survived millions of years" mechanic so I put it on a shark. It probably should be moved to an appropriate colour.

Good point. I was cautious because I knew the problems with dredge, but this shouldn't be any sort of problem.

Those abilities sound v close, it probably doesn't make a big difference how it's worded, I chose what I thought was simpler, but it could still be changed to trigger and/or go via the graveyard. (Not sure if it should be "put it into your hand instead of your graveyard" or "instead of dying")

Rules nitpick: Paying mana inside a replacement ability has unexpected rules trickiness because it can happen inside the middle all sorts of effects or costs... I think it'd be better if it said "When this dies, you may pay [cost]. If you do, return it to your hand."

Alternatively you could do ": The next time ~ would die this turn, return it to your hand instead", but then that's asking for the same kinds of problems that regeneration itself had.

Yes, lets assume we go with one of those variants :) (It originally didn't have a mana cost and then I decided it was always going to be better to have at least a small cost.)