1. A method of erasing data in a storage device, the storage device having one or more non-volatile memory devices, the method comprising: performing a plurality of memory operations including read operations and a first set of erase operations on portions of the one or more non-volatile memory devices specified by the read operations and the first set of erase operations, wherein the first set of erase operations are performed using a first set of erase parameters that has been established as a current set of erase parameters prior to performing the first set of erase operations; in accordance with each erase operation of at least a subset of the first set of erase operations, updating one or more erase statistics that correspond to performance of multiple erase operations; in accordance with a comparison of the erase statistics with an erasure performance threshold, establishing a second set of erase parameters as the current set of erase parameters; and subsequent to establishing the second set of erase parameters as the current set of erase parameters, performing a subsequent erase operation on one or more portions of the one or more non-volatile memory devices using the second set of erase parameters; wherein the method includes generating a count of how many erase operations of the multiple erase operations have durations that exceed a predefined duration threshold, wherein each erase operation erases one or more blocks of memory cells; and a respective erase statistic of the erase statistics corresponds to the count of how many erase operations of the multiple erase operations have durations that exceed the predefined duration threshold.