Я же писал выше.
Одна из моих реализаций 2004-го года в биллинговой системе делала так: в момент первого запуска включался счетчик. Шли запросы в базу по одному в цикле, счетчик считал интерации. По достижении 20 сек. цикл завершаем. У нас есть значение - количество интераций, которые удалось выполнить за 20 секунд. Следующий запуск делаем с учетом полученного значения.
Вы этот пример можете использовать в вашей работе. Алгоритм такой: отдаем клиенту JS-скрипт, который работает в паре с php-скриптом. JS делает запросы с периодичностью, скажем, 1 сек. Вам нужно замутить прогресс-бар. Вы перед первым запуском запрашиваете у базы общее количество строк, которые предстоит обработать. И пусть это значение - 100% вашего прогресс-бара. Запускаем первый цикл. В нем счетчик количества интераций, как я писал выше. Допустим, за 1 секунду выполнилось 5 запросов. Теперь вы уже можете посчитать и показать пользователю сразу несколько данных, а именно: текущее значение прогресс-бара и приблизительное время работы скрипта. При этом php запоминает в отдельном файле или передает в JS текущее положение указателя (например, обработаны строки с 1 по 5, начинать с 6). Далее JS периодически каждую секунду делает запрос к скрипту. И цикл повторяется, но уже без участия счетчиков (либо корректируем время завершения).
Следует помнить, что полученное количество интераций непостоянно и зависит от однотипности строк таблицы, от загруженности сервера, от погоды, от сексуальный предпочтений админа и т.п., поэтому берем не полученное значение интераций, а немного с учетом возможной погрешности, например, умножив на некий процент.
Вот и все.