Why is my SQL statement sometimes slow and sometimes fast?
This Answer has a mixture of explanation ("why" slow versus fast), speedup (how to be more efficient), and non-blocking (how to avoid the trouble with mysqldump).


If few rows are that old, the main effort is scanning the entire table.  This can be helped significantly via INDEX(date)
If more than 100K rows are that old, then the main effort is saving 100K rows in case of a undo (rollback).  This can be quite costly.  Don't do more than 1K at a time.
If the count is somewhere in between, then there is both the table scan and some of the undo effort.  Note that it may find rows to delete early in the scan, or late -- thereby making this take an unpredictable amount of time.


While the lengthy DELETE is running, other things may be adversely affected -- such as timeouts in mysqldump.  So, the goal is to keep the DELETE down to only a few seconds, both by speeding it up and by decreasing how much you bite off at a time.

My Big Delete blog explains several ways to significantly improve your task.

Note that one of my techniques focuses on what to do if you are deleting more than half the table.  This involves copying over the rows to keep.  (See the details on RENAME TABLE, etc)