We report the performance of coherently-detected nine-channel WDM transmission over high dispersion fibers, using polarization multiplexed m-ary quadrature amplitude modulation (m = 4, 16, 64, 256) at 112 Gbit/s. Compensation of fiber nonlinearities via digital back-propagation enables up to 10 dB improvement in maximum transmittable power and similar to 8 dB Q(eff) improvement which translates to a nine-fold enhancement in transmission reach for PM-256QAM, where the largest improvements are associated with higher-order modulation formats. We further demonstrate that even under strong nonlinear distortion the transmission reach only reduces by a factor of similar to 2.5 for a 2 unit increase in capacity (log(2)m) when full band DBP is employed, in proportion to the required back-to-back OSNR. (C) 2011 Optical Society of America