Images are relatively simple. They are static. And the libraries needed to manipulate images are built into PHP.
Videos are much, much different.
Either you need to encode the video yourself with an encoding/conversion tool to add a watermark, or utilize ffmpeg with an exec command like Ruble posted.
ffmpeg is usually a special request to add to a server. For shared hosting, hosts won't usually add it because it sucks up CPU time when in use and can slow down the other sites on the server. You'll typically need to be using dedicated server or VPS.