How large would the steam explosion at Chernobyl have been?

In my view the water isn't really the thing to focus on here. The real energy reservoir was the partially-melted core; the water wasn't dangerous because it held energy, but rather because it had the potential to act as a heat engine and convert the thermal energy in the core into work. We can therefore calculate the maximum work which could conceivably be extracted from the hot core (using exergy) and use this as an upper bound on the amount of energy that could be released in a steam explosion. The exergy calculation will tell us how much energy an ideal (reversible) process could extract from the core, and we know from the Second Law of Thermodynamics that any real process (such as the steam explosion) must extract less.

Calculation

Using exergy, the upper bound on the amount of work which could be extracted from the hot core is

\begin{align} W_\text{max,out} &= X_1 - X_2 \\ &= m(u_1 - u_2 -T_0(s_1-s_2)+P_0(v_1-v_2)) \end{align} If we assume that the core material is an incompressible solid with essentially constant density, then \begin{align} W_\text{max,out} &= m(c (T_1 - T_2) -T_0 c \ln(T_1/T_2)) \end{align} where $T_0$ is the temperature of the surroundings, $T_2$ is the temperature after energy extraction is complete, and $T_1$ is the initial temperature. At this point you just need to choose reasonable values for the key parameters, which is not necessarily easy. I used:

• $T_1 = 2800\,^\circ\text{C}$ based on properties of corium
• $T_2 = T_0$ as an upper bound (the most energy is extracted when the system comes to the temperature of the surroundings)
• $T_0 = 25\,^\circ\text{C}$ based on SATP
• $c = 300\,\text{J/(kg.K)}$ based on properties of UO$_2$
• $m = 1000\,\text{tonnes}$ based on the text in your question.

This gives me $W_\text{max,out} = 6.23 \times 10^{11}\,\text{J}$ or 149 tonnes of TNT equivalent. This is several orders of magnitude lower than the "megatons" estimate provided in your question, but does agree with your gut response that "megatons" seems unreasonably high. A sanity check is useful to confirm that my result is reasonable...

Sanity Check

With the numbers I used, the system weights 1 kiloton and its energy is purely thermal. If we considered instead 1 kiloton of TNT at SATP, the energy stored in the system would be purely chemical. Chemical energy reservoirs are generally more energy-dense than thermal energy reservoirs, so we'd expect the kiloton of TNT to hold far more energy than the kiloton of hot core material. This suggests that the kiloton of hot core material should hold far less than 1 kiloton of TNT equivalent, which agrees with your intuition and my calculation.

Limitations

One factor which could increase the maximum available work would be the fact that the core was partially melted. My calculation neglected any change in internal energy or entropy associated with the core solidifying as it was brought down to ambient conditions; in reality the phase change would increase the maximum available work. The other source of uncertainty in my answer is the mass of the core; this could probably be deduced much more precisely from technical documents. A final factor that I did not consider is chemical reactions: if the interaction of corium, water, and fresh air (brought in by an initial physical steam explosion) could trigger spontaneous chemical reactions, then the energy available could be significantly higher.

Conclusion

Although addressing the limitations above would likely change the final upper bound, I doubt that doing so could change the bound by the factor of ten thousand required to give a maximum available work in the megaton range. It is also important to remember that, even if accounting for these factors increased the upper bound by a few orders of magnitude, this calculation still gives only an upper bound on the explosive work; the real energy extracted in a steam explosion would likely be much lower. I am therefore fairly confident that the megaton energy estimate is absurd, as your intuition suggested.

The top accepted post (user1476176) has already done a thorough job of calculating the thermodynamics for a steam explosion (spoiler: nowhere near the megaton scale -- they were only off by 10,000X to 100,000X).

To compliment that, here's some intuition for what it takes to achieve a megaton-scale explosion, and why it is so laughably unrealistic to think that could happen by accident in even the worst-possible reactor disaster (i.e., Chernobyl):

1. It took our top scientists and engineers multiple years to achieve kiloton-scale bombs, and years more to achieve megaton-scale bombs using fusion. It was not easy, and they were working with billions to trillions of dollars of government resources at their disposal. If you could just drop some melted corium into water ... they would have done that at least once -- the first H-bomb test involved vaporizing a building-scale cryogenic chilling plant that was keeping the liquid deuterium from boiling away.

Making even kiloton-scale explosions requires precision.

Making megaton-scale explosions requires extreme precision, beyond the capabilities of many nation states. And fusion.

2. The largest pure-fission bomb ever tested was on the order of 0.5 megatons. They used huge quantities of weapon grade $^{235}U$ (>95% enrichment), surrounded by a neutron reflecting tamper, and almost instantaneously compressed to super-criticality by two different high-explosives precision engineered to produce a perfectly spherical shock wave. Chernobyl used fuel that was less than 2% enriched, meaning that 98% of it was non-fissile $^{238}U$, and that is before you account for contamination by fission byproducts, melted concrete, and melted steel.

3. Fusion is the only way that weapons engineers have been able to create megaton-scale explosions. And fusion is completely out of the picture here for at least two reasons:

• Bombs depend on fusing rare hydrogen isotopes like deuterium ($^2H$) and tritium ($^3H$) that weren't present at Chernobyl; for deliverable bombs, they use lithium-deuteride which contains deuterium and forms tritium under neutron bombardment (by cracking the lithium). The random fire-hose water that was seeping through Chernobyl was almost entirely (99.98%) composed of normal hydrogen ($^1H$), which is so hard to fuse that we don't / can't use it in bombs.
• Even to fuse $^2H$ and $^3H$, they have to use kiloton-scale fission bombs, combined with precision engineering that uses the fission bomb's x-rays to generate compression that's way beyond what's achievable with conventional explosives. This drives the $^2H$ and $^3H$ atoms together at extreme pressures and temperatures. It's extremely hard to do and, unlike with fission criticality accidents, fusion will never happen by accident. For example, if you moved the tritium from the center of the plutonium pit and just set it next to the bomb, it wouldn't fuse. Fusion is exceedingly difficult to achieve, on a level that's hard to put into words.

4. To achieve even kiloton-scale yields, great care must be taken to assemble the super-critical mass as quickly as possible, and to avoid stray neutrons that might start the chain reaction prior to the maximum compression (i.e., maximum super-criticality). For example, the first North Korean bomb attempt "fizzled" with a sub-kiloton yield ... generally, this happens for one of two reasons: either the implosion was less than perfect, or stray neutrons started the chain reaction before the point of maximum compression. Either way, what happens is that the fissile material, which is heating at an exponential rate, physically blows itself apart before the chain-reaction can achieve kiloton yields.

• Compression, compression, compression. The art of designing a nuclear bomb involves three things: Getting the the bomb into a maximally super-critical state (implosion), starting the chain reaction precisely at the moment of maximum criticality (the polonium/gold neutron initiator), and then keeping the fissile material super-critical state for as long as possible to maximize the yield (the "tamper" material slows the expansion by tens of nanoseconds). Note that none of these components were present at Chernobyl.

• Weapons Grade. To get good bomb yields, you want to use a fissile material that's as pure as humanly possible. Both being as close to 100% fissile material as possible (compared to Chernobyl's 2% fuel), as well as not being contaminated with neutron sources that will trigger an early detonation "fizzle". The Chernobyl corium contained highly active neutron emitters and would have instantly fizzled at the moment of criticality well in advance of achieving the super-criticality required for a kiloton-scale yield.

5. The neutron chain-reactions in a reactor are very different from those used in bombs:

• Thermal Neutrons - the only way to achieve criticality with Chernobyl's 2% enriched uranium is to use a neutron moderator, like graphite, that slows the neutrons emitted by fission until they are in the "thermal" spectrum (i.e., bouncing around at similar thermal temperatures to the surrounding atoms). This increases $^{235}U$'s neutron absorption cross-section and consequently, raises the probability that any given neutron will trigger another fission event rather than leaking out of the reactor core or being absorbed into some other atom. But because they need to bounce through graphite before slowly finding more $^{235}U$, thermal neutrons have much longer "doubling times" than do fast neutrons, meaning that the bomb-scale chain reactions just aren't possible: the critical mass will thermally blow itself apart as soon as even a tiny fraction of the material fissions.

• Delayed Neutrons - in addition to using "thermal" rather than "fast" neutrons, reactors are designed to operate "prompt sub-critical", meaning that the neutrons that are emitted from $^{235}U$ fission are insufficient for sustaining a chain-reaction unless one also includes neutrons generated from secondary decay chain events that occur seconds to minutes later. This is important because it makes reactors much easier to control. One of the key questions I have about Chernobyl is whether during the sheer incompetence that led to the initial reactor explosion, they managed to take the reactor into the "prompt criticality" regime, although with thermal neutrons that have to bounce around before chain-reacting, it becomes a more subtle distinction. I'm not sure if that's globally unknown, or just unknown to me.

A steam explosion between corium at 3000 degC and water would be pretty dramatic, potentially destroying additional containment elements, ejecting highly radioactive material onto the roof and grounds, and generally complicating the already hellish clean-up challenges. So no kidding, they wanted to avoid that.

But a steam explosion is nowhere near the megaton-scale energy release described in the show.

It's highly dubious that the Chernobyl corium, stripped of its moderating graphite and contaminated by concrete, steel, and especially Boron (a potent neutron absorber), could have even assembled into a critical mass at all.

But even if, by some crazy set of coincidences that did happen, the chain reaction of thermal neutrons in a barely critical configuration would have thermally blown itself apart well before reaching even the kiloton-scale range of energy releases. Megatons is laughable.

The show (which, overall, was AWESOME), was embarrassingly unfounded on this point. Chernobyl was awful enough in reality without the need to fear-monger with ludicrous hypotheses.

I had heard this scenario many years ago and its primary source I believe was an interview with Gorbachev were he mentioned it (I cant find the source though, so take with a pint of salt).

I too considered it to be without much foundation (Given the known facts its out right impossible unless they had stored nuclear weapons hidden under the cores foundation) and given that it comes out of a man that isn't a scientist but a politician, my best guess would be that the 3 megaton figure should not be considered as the yield of an explosion event but more likely the fallout equivalent of the radiation that would have been released after the steam explosion and the subsequent destruction of the remaining 3 cores at the vicinity