(which may not account for destroyed bills, I'm not sure).

The descriptions of M0 I see include holdings by the Federal Reserve of notes, and they seem to have a good handle on actively destroying degraded notes (http://www.federalreserve.gov/faqs/how-long-is-the-life-span-of-us-paper-money.htm), so I assume it does account for the destruction of old notes and printing of fresh notes to give a net M0. It wouldn't make much sense to count destruction but not creation, or creation but not destruction, or neither (since the first two guarantee an increasingly inaccurate M0 and the latter could cause accuracy issues if destruction were not pegged exactly to creation).