Multiple small deletes
I'd consider:


If the table is partitioned - to disable the index partitions on the specific partitions which are going to be changed, and rebuild (rebuild online probably) them after the operation. 
Increase the amount of memory in disposal (for the specific session), so that it won't do any I/O operations (on temporary tablespace) at all, by changing workarea_size_policy to 'manual' and  sort_area_size, hash_area_size to the maximum size you can spare for this operation. 
Run the entire operation using parallel hint (or parallel_index if you'd decide to use some indexes after all). 
Switch all the accessed objects to nologging mode, so that redo logs won't be generated during the operation (and switch back to logging right after it's finished of course).