We have observed Markarian 421 in January and March 2001 with the CANGAROO-II imaging Cherenkov telescope during an extraordinarily high state at TeV energies. From 14 hours observations at very large zenith angles, $sim70^circ$, a signal of 298 $pm$ 52 gamma-ray--like events (5.7 $sigma$) was detected at $E>10$ TeV, where a higher sensitivity is achieved than those of usual observations near the zenith, owing to a greatly increased collecting area. Under the assumption of an intrinsic power-law spectrum, we derived a differential energy spectrum $dN/dE = (3.3 pm 0.9_{stat.} pm 0.3_{syst.})times10^{-13} (E/10 {Te V})^{-(4.0 ^{+0.9}_{-0.6}_{stat.} pm 0.3_{syst.})}$ ph./cm$^2$/sec/TeV, which is steeper than those previously measured around 1 TeV, and supports the evidence for a cutoff in the spectrum of Markarian 421. However, the 4 $sigma$ excess at energies greater than 20 TeV in our data favors a cutoff energy of $sim$8 TeV, at the upper end of the range previously reported from measurements at TeV energies.