Dark matter decaying or annihilating into mu+mu- or tau+tau- has been proposed as an explanation for the e+e- anomalies reported by PAMELA and Fermi. Recent analyses show that IceCube, supplemented by DeepCore, will be able to significantly constrain the parameter space of decays to mu+mu-, and rule out decays to tau+tau- and annihilations to mu+mu- in less than five years of running. These analyses rely on measuring track-like events in IceCube+DeepCore from down-going nu_mu. In this paper we show that by instead measuring cascade events, which are induced by all neutrino flavors, IceCube+DeepCore can rule out decays to mu+mu- in only three years of running, and rule out decays to tau+tau- and annihilation to mu+mu- in only one year of running. These constraints are highly robust to the choice of dark matter halo profile and independent of dark matter-nucleon cross-section.