Missingno is not a real Pokémon, but is treated as such by the game. This makes the game execute code it shouldn't execute, which in turn causes all sorts of undefined behavior, including tampering with save files.
To understand why Missingno alters already existing savegames, one must first understand how Gameboy games work.
On the Gameboy, savegames are saved on the cartridge's RAM (Random Access Memory), which requires a battery to keep its data. The game itself is stored on ROM (Read Only Memory).
Back then, games had complete control over both the console's hardware and the cartridge. There was no OS (Operating System) running on the console which the game had to communicate with. If the game said "jump", the console would (if it could), even if the order made no sense at all. This allowed games to include additional hardware in the cartridge to allow the console to do what it couldn't normally do, like add 3D capabilities. It's a feature that was hardly ever used, since it would've made cartridge costs skyrocket.
So how does Missingno corrupt savegames in the first place? The answer is simple: Missingno is not part of the game. Let me explain in a bit more detail.
Whenever you reach an area in Pokémon, the game would load a list of Pokémon you could encounter in that area. Not all areas have tall grass or water where you could catch Pokémon, so not all areas would have that list.
Cinnabar Island and Viridian City are two such areas; with no tall grass or water, there is no need for a Pokémon list, right? Well, that's not true for Cinnabar island. There is this one column of water at the Eastern end of the island that still belongs to the island itself. Since the devs overlooked that patch, they didn't bother giving Cinnabar island its own Pokémon list. This is why you could encounter Safari Zone Pokémon at Cinnabar island. Since Fuchsia City also doesn't have a list, leaving the Safari Zone doesn't reset it, making Safari Pokémon encounterable at Cinnabar island.
So what's the deal with the old man of Viridian City and Missingno? Remember what the old man does? He teaches you how to catch Pokémon, but you can't actually encounter any Pokémon in Viridian City. Because of that, the devs had to load some special data into that list to ensure the old man could have a scripted battle in which he'd quickly catch his target. That data is later interpreted as a real Pokémon at Cinnabar island, and rendered as Missingno.
This is where it gets technical: Since the data that had been loaded in the Pokémon list by the old man isn't actually a Pokémon, the engine would try to execute part of the code it's not supposed to execute. This is quite similar to how malware works, only it's not a malware but a glitch. At this point, there is no telling what the game could do. The game could theoretically overwrite your savegame with all zeroes (deleting your save in the process), or corrupt it beyond recognition, or sit down and drink tea, or ignite all the nukes worldwide (slight exaggeration).
Since RAM is very easy to access, savegame corruption isn't very unlikely. And luckily, since the game itself is stored on ROM, all you need to do is start a new game and avoid Missingno this time around.