The software to try depends on the OS on your mobile. Is that iOS (on an iPhone), Android or Windows Mobile?

If it's, say, Android, google for DATA RECOVERY ANDROID and try a few of the programs that are found. Success, however, isn't guaranteed.

If you deleted the video from an SD-card and you can take that out, and you have a SD-card reader on your PC or laptop, it's a far better idea to talke the SD-card out and try Windows programs like Recuva (free).