Cita: La duda en si es si esto puede tomar mucho tiempo?
Obviamente sí,
¡son millones de registros en un loop! 
Definitivamente sí.
Ejecutar dichos procesos desde el navegador sería lo más grave.
Cita: mostrarle un simplemente "Le enviaremos un mail cuando este terminado" o tal ves un "PDF terminados, puede cerrar la ventana y continuar con sus tareas".
Usando cronjobs es muy simple, un proceso del sistema ejecuta tus scripts en segundo plano y eventualmente ya puedes notificar al usuario por otros medios, etc.
Cita: no toma ni dos segundos hacerlo pero cuando son millones
Obvio: multiplica 1s x 1000000 y sufre.
