Add a microlfow that etrieves the records from the database with a custom range for example 500 and create a loop like below, checking first if the retrieved list is not empty and then delete the retrieved list. When the lsit is empty there are no more records to delete and the microflow finishes.
Hope this helps you implement this.