We describe the relationship between the notions of M-regular sheaf and GV-sheaf in the case of abelian varieties. The former is a natural strengthening of the latter, and we provide an algebraic criterion characterizing it among the larger class. Based on this we deduce new basic properties of both M-regular and GV-sheaves. In the second part we give a number of applications of generation criteria for M-regular sheaves to the study of Seshadri constants, Picard bundles, pluricanonical maps on irregular varieties, and semihomogeneous vector bundles. Thi