41 pages, 21 figures, 4 tables. v2: Model corrected at small and negative xF (section 3.1), conclusions unchangedThe effects of parton energy loss in cold nuclear matter on heavy-quarkonium suppression in p-A collisions are studied. It is shown from first principles that at large quarkonium energy E and small production angle in the nucleus rest frame, the medium-induced energy loss scales as E. Using this result, a phenomenological model depending on a single free parameter is able to reproduce J/psi and Upsilon suppression data in a broad xF-range and at various center-of-mass energies. These results strongly support energy loss as the dominant effect in heavy-quarkonium suppression in p-A collisions. Predictions for J/psi and Upsilon sup...