You can do it by a terminal command in a directory where these files are located.
rename 's/^video_//' *.mp4
That means select all filenames started with
video_ and replace
video_ with nothing. I guess
s is for "substitute".
^ shows the beginning of string. If you omit
^, the first occurrence of
video_ will be removed no matter where it is located in the string. But in your case it does not really matter.
Note: Ubuntu versions above 17.04 don't ship with
rename package, however you can still install it from default repositories via
sudo apt install rename