if you have the BFN SuiteApp "SAFE" guide for reference, there is a section Using Parent-Child Relationships to Perform Mass Create/Update
you can potentially use similar "hack" of creating dummy parent-child relationship to execute mass delete in bulk as well (where only involves adding/removing Custom record as children to dummy parent, so is much less governance and I assume quicker performance in theory)
just threw together a mock script in demo account, created 10K custom records in ~1.5min and deleted them in ~1min just via script debugger using this method, but individual account performance might vary