Você pode fazer isso por um comando terminal em um diretório onde esses arquivos estão localizados.
rename 's/^video_//' *.mp4
Isso significa selecionar todos os nomes de arquivos iniciados com video_ e substituir video_ por nada. Eu acho que s é para "substituto".
^ mostra o começo da string. Se você omitir ^ , a primeira ocorrência de video_ será removida, não importando onde ela esteja localizada na string. Mas no seu caso isso não importa realmente.