В общем случае, если не указан порядок сортировки ORDER BY, то один и тот же Select может возвращать данные в разном порядке, поэтому первых N записей действительно могут быть разными для одного и того же Select-а.
В предложенной ситуации, при том что условие Where *совпадает* для обоих операторов Select и Delete, оператор Delete удалит все или только часть (если записей больше 5000) записей которые могут быть возвращены Select-ом. То есть удалит подмножество оператора Select. Так как необходимо было удалить все (1`000`000) записи которые удовлетворяют where, то при таком подходе рано или поздно они удалятся, что и требовалось.