We will likely never know precisely how Fermi made his estimate, but we can make some reasonable guesses. We do know that he depended on more serious theoretical work than is usual for what now are considered typical "Fermi problems". His great insight was realizing that applying that theory to a very simple physical system - dropped bits of paper in a blast wave - would allow him to roughly determine the yield of the Trinity explosion. Sometimes one can only confidently make things simple by deeply understanding the complexities.
TLDR version: Fermi used the best relevant hydrodynamic theory available at the time. Before the blast, he calculated the expected pressure wave air displacements for various explosive yields. When he observed how far his pieces of paper travelled, he could immediately estimate the yield from his pre-prepared table. Following what is likely the same theory, and using Fermi's observation and reasonable values for the other input parameters, we can get an answer consistent with Fermi's estimate that the yield corresponded "to the blast that would be produced by ten thousand tons of T.N.T."
Note that a recent paper, Fermi at Trinity, follows a slightly different path than I do here but ends up with similar conclusions. Let's start.
Fermi problems are traditionally solved using common knowledge and basic principles, but Fermi's "common knowledge" was broader and deeper than most.
Murray Gell-Mann said that Fermi "kept a little notebook with useful formulas … that allowed him to tackle a lot of practical problems on simple request, because he had worked them out before and some of the critical formulas were in his little book."
Fermi's dropped paper method was carefully thought out ahead of time. Emilio Segrè, who was with Fermi at Trinity, tells us that before the blast, Fermi had prepared "a table of numbers, so that he could tell immediately the energy liberated from this crude but simple measurement."
In particular, Fermi was undoubtedly familiar with the lectures on Shock Hydrodynamics given at Los Alamos 9 months before the Trinity test by Hans Bethe, Klaus Fuchs, John von Neumann, Rudolf Peierls, and
William Penney.
In the last of these lectures, Bethe presented a semi-acoustical method for treating weak shock waves, and most of the physics Fermi needed for his yield calculation was in Equations 381, 413, 420, and 429 in that lecture. I will mostly use the notation from that lecture.
The energy $E$ of a weak hemispherical blast pressure wave with half-wavelength thickness $L$ observed at distance $R$ from the bomb is
$$E=\frac{2}{3}\frac{2\pi R^2 }{\rho_1 c_1^2}(\Delta P)^2 L\tag{Eq. 420'}$$
where $\rho_1$ is the density of air, $c_1$ is the speed of sound, and $\Delta P$ is the peak pressure in the wave at distance $R$. This Eq. 420' is reduced by a factor of 2 compared to the original Eq. 420 which is for a spherical wave. The Trinity explosion was at ground level, so the blast wave was approximately hemispherical.
The intuitive origin of Eq. 420' can be seen by rewriting it as
$$E=\frac{2}{3}(2\pi R^2 L \rho_1)\left(\frac{\Delta P}{\rho_1 c_1}\right)^2=\frac{2}{3} M_{shell} \Delta v^2 =\frac{4}{3} K_{shell} \tag{Eq. 420''}$$
$E$ is almost exactly the naive kinetic energy $K_{shell} $of the blast shell, where $M_{shell}$ is the mass of a hemispherical shell of air of radius $R$ and thickness $L$. The peak displacement velocity $\Delta v$ of air in the blast wave is related to $\Delta P$ by the usual relationship for acoustic impedance
$$\Delta P = \rho_1 c_1 \Delta v \tag{Eq. 381}$$
This could be determined from the horizontal displacement $D$ of the air in the blast wave and the time $\Delta t$ it took for the wave to pass:
$$\Delta v = 2\frac{D}{\Delta t}$$
The factor of 2 is the ratio of the peak to average velocity of the expected sawtooth shaped pressure wave that arrives abruptly and then falls off linearly as shown in Figure 27c of the lectures.
Bethe's theory is for weak shock waves far from the explosion where the blast has decayed to an acoustic wave so
$$L=c_1 \Delta t \qquad \rightarrow \qquad \Delta v = 2\frac{D c_1}{L}$$
and we can finally rewrite Eq. 420 as
$$E=\frac{16}{3} \pi R^2 c_1 \rho_1 \left(\frac{D}{\Delta t} \right)^2 \tag{Eq. 420'''}$$
When the blast wave arrived as Fermi was dropping his bits of paper, the pieces sudden horizontal movement was a direct measure of $D$. How long the horizontal movement took would be a measure of $\Delta t$.
In his blast observations report, Fermi noted that "I could observe very distinctly and actually measure the displacement of the pieces of paper that were in the process of falling while the blast was passing. The shift was about 2 1/2 metres, …"
So $D=2.5\,\textrm{m}$, but the time duration of the pulse is not mentioned.
It is possible he did note the time and the table he had prepared ahead of time was a grid for different values of $D$ and $\Delta t$, but in that case wouldn't he have included $\Delta t$ in his memo? Maybe Fermi wanted a method he could easily do by himself, while recording $\Delta t$ would be best done by enlisting helpers . (As we'll see, the pulse was a couple of seconds long, so careful observers with stop watches could likely have measured $\Delta t$ with as precision comparable to $D$.)
Assuming Fermi's yield estimate was based only on $D$, then it is likely he used more "early theoretical hydrodynamic calculations" to estimate or eliminate $\Delta t$. According to Bethe,
$$L = \frac{\gamma+1}{2 \gamma} R \frac{\Delta P}{P_1} \ln{\frac{P_1}{\Delta P}} \tag{Eq. 413}$$
where $\gamma = 1.4$ is the specific heat ratio of air.
Using $\Delta t = L/c_1$, this equation this gives $\Delta t = 2.3\,\textrm{s}$ for $\Delta P \approx 0.16 \,\textrm{psi} = 1.1\,\textrm{kPa}$ for a $10000\,\textrm{ton}$ TNT explosion, interpolated from Joseph Hirschfelder's report on Estimated blast pressures from TNT charges of 2 to 10000 tons.
This is compatible with the several seconds (depending on their size and shape) that small pieces of paper take hit the ground when dropped from $6\,\textrm{feet}$.
Rearrangements and substitutions give
$$\Delta t = \frac{\gamma+1}{2 \gamma} R \frac{2 R \rho_1 c_1 D}{P_1 \Delta t} \ln{\frac{P_1 \Delta t}{2 R \rho_1 c_1 D}} \tag{Eq. 413'}$$
It is plausible that before the blast Fermi solved this nonlinear equation for $\Delta t$ for various values of $D$, which Eq. 420''' could turn into blast wave energies $E$. (Readers younger than me might be surprised by what we used to calculate and solve with a paper, pencil, and slide-rule.)
The blast wave does not carry all the energy of the explosion, so in his table, Fermi would want the actual explosive yield $E_0$, not just the blast wave energy $E$ in the blast wave. According to Bethe, these are approximately related by
$$E_0\approx 3E\sqrt{\ln P_1/\Delta P} \tag{Eq. 429}$$
where $P_1$ is ambient atmospheric pressure.
We are finally ready to estimate the yield. The temperature and pressure at the time of the explosion at the 1500 metre altitude test site were 71 F (22 C) and $P_1 = 85\,\textrm{kPa}$, so we'd expect $c_1 \approx 343\,\textrm{m/s}$, and $\rho_1 \approx 1.01\,\textrm{kg/m}^2$. Fermi was about 10 miles ($R=16\,\textrm{km}$) from the explosion, and his observation of $D=2.5\,\textrm{m}$ gives an estimate of $\Delta t = 1.9 \,\textrm{s}$, $E = 4.5\,\textrm{TJ}$, and a yield of
$$E_0 \approx 31\,\textrm{TJ} = 7\,\textrm{kilotons}$$
There may be, however, one final correction. How did Fermi define a TNT equivalent ton? Every reference to "ton" at Los Alamos seems to mean 2000 pound "short ton", but I have used the modern TNT equivalent that is based on "1000 kilograms". If Fermi used the 2000 pound ton, then his "ten thousand tons" would correspond to nine kilotons by the modern definition. Conversely, our calculated yield becomes
$$E_0 \approx 8 \textrm{ thousand "tons" of T.N.T}$$
It is worth emphasizing that there are too many uncertainties to mention in all this (not even counting any mistakes I might have made).
For example, Fermi may have made some different theoretical and experimental choices in building on Bethe's work, which already had lots of assumptions and simplifications. Did "2 1/2 metres" mean $2.5\pm 0.5 \textrm{m}$, or maybe "1/2 metre" was the step size in his pre-calculated table? (It takes little more than a 1/4 metre shift in $D$ for our calculation to give $E_0=10\,\textrm{"old" kilotons}$.)
I'd be surprised if Fermi trusted his estimate to better than a factor of two (if that), so it is plausible that Fermi might have rejected "8" as implying spurious accuracy, and instead preferred to state that the yield corresponded "to the blast that would be produced by ten thousand tons of T.N.T."
It is perhaps ironic that I (and others) have spent so much effort trying to precisely reproduce Fermi's estimate, when it became the archetype for imprecise "Fermi Problems" where we are often happy with order-magnitude accuracy.
The original official estimate for the Trinity Yield was 18.6 kt, and the most recent careful assessment is $24.8\pm 2$ kt. Fermi's quick value is impressively consistent with both. I wish all my rough estimates were as accurate!