There were several forces behind the seemingly ridiculous stockpile sizes in the Cold War.
One is to keep in mind that "stockpile size" and "strategic force deployments" are not the same thing: most of those warheads were not deployed at any given time, but were spares, backups, extras, etc. Here are some graphs that show different ways of parsing out the "what was actually deployed" data, which can be compared to the "what was the size of the stockpile" data. You can see that far more were in the stockpile than were deployed.
Second, it is worth keeping in mind the types of weapons varied. These were not all thermonuclear bombs — some were small tactical weapons meant to attack tanks, bombers, boats. That big rise in warheads you see in the 1960s was mainly from tactical weapons, which were dispersed globally. Once you start thinking about nukes as things that would be small, and destroy "small" things, then you start to imagine reasons to have thousands of them.
Third, once the superpowers entered into the era of "nuclear plenty," where they could produce thousands of weapons, their choices of targets got larger. You've got enemy cities/industrial sites/economic areas/etc. You've got enemy military bases, including the nukes they are aiming at you or your allies. You've infrastructure that might be dual-use (airplane runways can be used by bombers, so if you're being complete, you crater those too). You've got the entire military infrastructure that most people don't pay attention to: radar dishes, antennae, fuel depots, refueling bases, communication hubs, etc., all of the things that make a nuclear attack possible in the modern age.
Depending on your targeting philosophy, it's easy to have thousands of targets. If you're just trying to discourage someone from nuking you, maybe you only target their cities. If you're trying to maybe take down their ability to wage war against you, then you have to target a lot more than that.
Fourth, targeting strategy doesn't work the way most people think it does. They think: one target, one nuke. In general, that's not the way it goes. Why not? Because each target requires a certain amount of blast pressure to destroy. Sometimes that is not that much, by nuke standards — a city is pretty vulnerable. But if it's a military installation, it's going to require more blast pressure than a house. If it's a missile silo, it'll require a whole lot.
Nukes are powerful but not infinitely powerful. They have limited areas over which they can put blast pressure (and fire, and radioactivity, but it's the blast pressure that is usually used for damage assessment). Higher blast pressures are even smaller areas. You can increase the size of these areas with bigger nukes. But it makes it harder to get them from point A to point B — the more powerful the nuke, the heavier and larger it is, generally (it's not a perfectly linear relationship, because there are tricks to make them more efficient).
Now you couple that with the accuracy of your delivery vehicle. Let's say you have a relatively small but hard target — let's say the bunker under the Kremlin. The main Kremlin building is about 300 m across. Let's say we're aiming a Titan II missile at it — a 9 megaton warhead (huge), but with an accuracy of only 900 m CEP (50% chance of hitting a point target within 900m). If the Kremlin requires, say, 600 psi of blast pressure to destroy, and our Titan II has a 100% reliability, that means we've got a 59% chance of total destruction of the target, 15% chance of partial destruction, and 26% chance of failure. If we want to have a 95% certainty of its total destruction, we'd need send 4 missiles at it.
If we drop our estimate of the missile reliability to, say, 80%, now we need 5 missiles. If we increase the amount of blast pressure needed to 1000 psi, now we need 6 missiles. If our warhead was smaller, say, 3 megatons instead of 9 Mt, we'd need 9 missiles with that amount of accuracy. Conversely, if our missile was much more accurate, we could get away with less yield. The Trident D5 has a CEP that is 10 times more accurate than the Titan II (90 m), and with only one 475 kt warhead could guarantee 1000 psi on an area the size of the Kremlin to 95% certainty.
These numbers were generated by my MISSILEMAP, which is a tool I made for showing these kinds of relationships and asking these kinds of questions. The reason for very high yield weapons was originally because the accuracy and system reliability were low. Today we use far fewer weapons but actually have much higher "lethality" — US weapons are more likely than ever to actually be able to destroy their targets, even though we have fewer weapons and they are lower yield, because the accuracy is much higher and the systems are more reliable.
Anyway — you can see how running this logic through will get you huge warheads counts; if it takes 6 missiles just to destroy the Kremlin to that high degree of certainty, imagine how it works out for other targets.
Do you have to think about nukes this way? No. But this is how the US strategists tended to think about it. And the Soviets too, to a certain extent (in general, the Soviets seemed more comfortable with uncertainty than the US did, but their missiles were lower in accuracy so that resulted in much larger yields being fielded). The Chinese, by comparison, have tended to see things differently: they don't pretend to be able to take out the US or USSR/Russia, so they keep a small force that is useful mainly as a threat to cities. Could the US or Russia do the same? Sure — except for the fact that they each have so many nukes now that for one side to radically reduce might put things out of balance. But one could imagine, in some happier future time, the US and Russia deciding they felt "safe enough" with only 200-300 nukes or so, as opposed to the several thousand we still have. (At the moment, the trends are starting to go in the other direction, towards a "new" arms race, but that's a different story.)
Lastly, separate from all of this high-strategy, it is important to acknowledge that in the US, anyway, there were other, "non-rational" forces at work. One of these is that for much of this history these weapons deployments were not under a lot of oversight: the decisions were made in secret by small numbers of military analysts, and not coordinated between branches of the military. This also led to interservice rivalries — Army vs. Air Force vs. Navy — that led to a duplication of efforts, and a redundancy of weapons that was linked to prestige and funding. In the 1990s the US took a fresh, post-Cold War look at its targeting policies and found that huge numbers of targets could be reduced, and that a lot of warheads and launchers could be eliminated.
And, of course, there were political forces, especially in the early Cold War, that emphasized quantity, sometimes over quality. Some of those deployed systems were dangerous and unreliable (the Jupiters in Turkey were a famous example of this, but the first generation Polaris missiles were also probably duds). They were pushed into deployment anyway because of fear and international competition. In retrospect we are probably lucky there were fewer accidents involving them than occurred, and that the accidents were worse than the ones that occurred. But the people doing this really believed that the more nukes we made and deployed, the safer we were. It wasn't until some time into the late Cold War that they really took seriously the idea that more nukes might make things more dangerous, especially those that are deployed without adequate security, safety, or surety protections.
This is a big topic and I've only skimmed it. If you want to get into the heads of the Cold War weaponeers, Schlosser's Command and Control is good and readable. If you want to get into the weeds regarding the history of the accuracy/yield/CEP/etc. issue, see MacKenzie's Inventing Accuracy.