Puedes usar las funciones de control del buffer de PHP para ir "tirando" al navegador la información del proceso que está haciendo PHP ..
Un ejemplo básico sería:
Código PHP:
for ($i=0; $i<=1000; $i++){
echo $i;
flush(); // Entramos al navegador todo lo q tenga hasta el momento PHP generado para la salida ..
}
Observa como funciona .. Se va "imprimiendo" el número de ese contador a medida de que se va generando por PHP y no todos de una vez como lo hace PHP por defecto (salvo q tengas el flush forzado .. no recuerdo la directiva exacta ahora ..)
Más info sobre el buffer de salida de PHP.
http://www.php.net/manual/en/ref.outcontrol.php
Con esto ya mas o menos podrías hacerte algo que simule una barra de progreso generando el HTML necesario. Tal vez te haga falta algo de javascript adicional ..
Un saludo,