There is an ugly bug somewhere which inflates the DB to monstrous sizes. It is somehow storing the rules repeatedly. I have already reported it few months ago. Now it could be the cause of slow rules deletion.

The rules table reaches hundreds of thousands records, and by my estimation it makes up more than 90% of the database size.