How do you design novel game mechanics?

The first is the original snake game. I'm not sure how it was invented in the first place to have the snake die if it collides with itself.

Wikipedia credits Blockade as the two-player predecessor to Snake which introduced the rule that snakes die if they collide with themselves. (Though it may have been hit on independently by several people, for the purposes of this answer let's ignore them.) Game designer Lane Hauck was studying random walks and wrote a simple computer simulation to explore their behaviour. The variation where the random walk can't revisit spaces it's been to before had some unexpected behaviour since it trapped itself very easily. He developed it into a video game.

Blockade being a two-player game, the question naturally came up about how to design a single-player variant. Some versions of Blockade had a single-player mode which was just the multiplayer game with NPC opponents. But several single-player games would take their ideas from it, and Snake was only one of them -- for example we can reasonably consider Qix to be a Blockade variant as well.

There is no original "seed" idea that came from nowhere. slither.io comes from Snake, Snake comes from Blockade, Blockade comes (now leaving the video game world) from 2D lattice random walks, which come from random walks more generally, which etc. etc.

On the other hand, specific elements of that design were added in response to a design need. Why does the snake's body in Snake become passable again once a certain amount of time has passed? Because it's easy to trap yourself after a certain amount of time in single-player Blockade and far too obvious that you are inescapably trapped, and a moving tail makes the strategy more interesting. Why does the snake's tail move at the same speed as its head? Because it makes physical sense that a real-world snake has a body of a certain size -- Blockade was a purely abstract game, but physical metaphors help players understand the game. Why does the snake get longer as you play the game? Because the game needs to get harder as you keep playing -- Blockade had the usable space naturally get smaller as your blocker filled it up, which gives it a difficulty curve, but a constant-size snake doesn't have that. Why does the snake need to eat apples to grow? etc.

New design elements are invented to solve problems with the game.

Sometimes this leads to amusing throwbacks. Snake is a single-player version of Blockade, but slither.io is a multiplayer version of Snake. Some parts of Snake that were added to make single-player gameplay fun are now finding themselves recontextualised in slither.io. And so the next generation of ideas is born.