Why is the GZK cutoff at such high energies?

Just look at the relativistic kinematics of what you know. As often in such problems, utilizing Lorentz invariants allows computation in different frames without ever performing an explicit Lorentz transformation.

For the reaction $$ p+gamma_{CMB} to p+ pi,$$ the before-and after total (E, p) vectors must be identical, and, crucially, their relativistic invariants $E^2-p^2$.

So, the r.h.side one, in its center of momentum frame, cannot be below threshold $(m_p+m_pi)^2$; so likewise the l.h.s., but now in the CMB frame, being an invariant,
$$ left(sqrt{m_p^2+p^2}+kright )^2 -p^2 -k^2 +2 p k approx m_p^2 +4pk, $$ where p is the cosmic proton momentum and k the CMB photon energy, so $10^{-3}$eV to $10^{-4}$eV. The optimal scenario, naturally, is proton-photon head-to-head collision, the origin of the + sign on the l.h.s.

Consequently, $$ pgeq frac {(m_p+m_{pi})^2-m_p^2}{4k} approx 10^{20} eV. $$

Now the reaction really goes strong on the Δ resonance, $ p+gamma_{CMB} to Delta^+$, which raises this threshold by another pion mass, ($M_Delta sim m_p+2m_{pi}$), but that's hardly a big deal, a factor of 2.1 larger than the above cutoff.

You are then advised to plug in reasonable numbers to finesse the answer. The peak of the CMB spectrum is around 7 $cdot 10^{-4}$ eV. So, in any case, the cutoff is handfuls of joules. This is evidently the obverse of the fundamental relativistic principle you learned about, favoring colliding beam experiments. Even though you have a colliding event on the l.h.s., it is the center of momentum frame on the r.h.s. that has the "low" energy and that matters when it comes to new matter (pion) production. The bulk of the primary proton energy in the CMB frame is "wasted" into bringing it to the center of momentum frame, blue-shifting the photon.