5 millones de registros para una tabla MySQL es un montón.
Asegurate de estar indexando bien la tabla.
Para empezar crearía un index "titulo, idvideo" o si el campo idvideo es más corto, mejor que el index sea: idvideo, titulo y en el WHERE primero ponés idvideo y después titulo.
Igual, vuelvo a repetir, 5 millones es muy groso para MySQL.
Edito:
Además el segundo SELECT lo podés obviar y tomar el id con mysql_insert_id;
sería así:
Exactamente después del INSERT