Delete millions of rows, fast
As mustaccio states, partitioning the data may help, though that might not be practical as a quick solution and you'd still have to optimise such statements a bit.

mysql is said to be particularly inefficient with IN clauses, in this case it may be running that inner query once for every row in mytable which is not going to be efficient. Better but still far from optimal, it may be running the inner query and spooling the results into a temporary table on disk then joining on that.

To avoid IN, you can rearrange actions of the pattern:

DELETE FROM mytable1 WHERE value IN (SELECT key FROM mytable2 WHERE &lt;filtering_condition&gt;)


into 

DELETE t1 
FROM   mytable1 t1
INNER JOIN
       mytable2 t2 
ON     t2.key = ti.id 
WHERE  &lt;filtering_condition&gt;


(in your case both mytable1 and mytable2 are the same table, and that works just as well)

I'm not sure how this will react to the counting-in-a-variable syntax you have there though (I'm not a mysql person specifically and that is not something seen in other DBs I do work with regularly).

If you add an integer identity column (I assume your PK here is id, time hence the current integer ID is not unique) then simply checking it against modulo 5 may be an acceptable approximation of "delete 80% evenly" like so:

DELETE t1 
FROM   mytable t1
WHERE  t1.time &lt; "2013-08-08 00:00:00"
AND    t1.counter MOD 5 != 0


Adding that column initially will be a time consuming process but maintinaing it afterwards should not be a problem (the DB will generate a number for you on each insert, just make sure you don't include it in the VALUES list of any INSERT operation), but you don't need to use IN or JOIN at all. An index over time, counter (instead of just time) may help performance a bit more. I would be tempted to make counter the primary key and id, time a seperate index (as well as an index over time or time, counter), but that would depend a lot on your other operations on the data.

Of course once you are altering the table structure like this, do give consideration the the partitioning option too. It will be more complicated but may have significant beneficial performance impact elsewhere too.