We discuss that hadron-induced atmospheric air showers from ultra-high energy cosmic rays are sensitive to QCD interactions at very small momentum fractions x where nonlinear effects should become important. The leading partons from the projectile acquire large random transverse momenta as they pass through the strong field of the target nucleus, which breaks up their coherence. This leads to a steeper x_F-distribution of leading hadrons as compared to low energy collisions, which in turn reduces the position of the shower maximum Xmax. We argue that high-energy hadronic interaction models should account for this effect, caused by the approach to the black-body limit, which may shift fits of the composition of the cosmic ray spectrum near the GZK cutoff towards lighter elements. We further show that present data on Xmax(E) exclude that the rapid ~ 1/x^0.3 growth of the saturation boundary (which is compatible with RHIC and HERA data) persists up to GZK cutoff energies. Measurements of pA collisions at LHC could further test the small-x regime and advance our understanding of high density QCD significantly.