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.