MySQL DELETE becomes exceptionaly slow with a large number of rows
With InnoDB, deleted rows must be held in case there is a crash or other reason to rollback the action.  This is costly, and may get more costly with larger counts, as you are seeing.

Plan A:  Delete in smaller chunks and COMMIT after each chunk.  (Similarly, chunking should be applied to Updates.)

Plan B, C, D, ...  See more tips

If no WHERE

No WHERE?  It would be much better to create a new table, then use RENAME TABLE to atomically swap the new one into place.  And finish with DROP TABLE.  No down time; no costly delete.

Query rewrite

If you are running 5.7, there is a new feature there which lets you "rewrite" queries to accommodate various kinds of nasties.  More discussion.  You could probably turn a delete without a where into DROP and CREATE.  (This is not quite as good as the previous suggestion.)