Thanks guys, here's the information you requested:
psql:postgres@cipafilter = show work_mem; work_mem ────────── 10MB (1 row)
OK, new theory then. Do you have triggers on or foreign key constraints to the table you are deleting from? It queues up each deleted row to go back and fire the trigger or validate the constraint at the end of the statement. You might need to drop the constraint, or delete in smaller batches by adding some kind of dummy condition to the WHERE clause which you progressively move.
Or select the rows you want to keep into a new table, and then drop the old one, rename the new one, and rebuild any constraints or indexes and other dependencies. This can be pretty annoying if there a lot of them.
