In effective single-electron theories, self-interaction manifests itself through the unphysical dependence of the energy of an electronic state as a function of its occupation, which results in important deviations from the ideal Koopmans trend and strongly affects the accuracy of electronic-structure predictions. Here, we study the non-Koopmans behavior of local and semilocal density-functional theory (DFT) total energy methods as a means to quantify and to correct self-interaction errors. We introduce a non-Koopmans self-interaction correction that generalizes the Perdew-Zunger scheme, and demonstrate its considerably improved performance in correcting the deficiencies of DFT approximations for self-interaction problems of fundamental and practical relevance.