I have lots of video files and am running out of storage space fast. Without affecting the quality too much, what is an easy quick way to re-encode these files to smaller files?
The original files are MP4 files from my camcorder.
Have a look at DeVeDe video creator. It's in the repositories and I've used it for making .iso files prior to burning them to disk. Most photographers/vidographers would shudder at the thought of permanently altering the original since anything you do to is is going to change or degrade it in some way. The MP4 is already a compressed format, so any further compression you achieve is going to be lossy.
Consider backing up your important original files on an external medium to free up space on your hard drive. I'd recommend a portable hard drive - I actually have two hard drives with my original photographs and all subsequent work. One is used as an off-site backup and gets rotated regularly with the current backup.
I recommend backing your videos up to an external Hard Drive, but if you can't or don't want to do that, WebM is the smallest video format I've come across. I use Oggconvert to convert video files (like MP4) to ogg and WebM.
To convert an MP4, select 'source' and locate the file you want to convert..
After you have selected your file, change 'video format' to 'VP8'. Then open the 'advanced' panel and change 'File Format' to 'WebM'.
Then click convert.
A 256MB MP4 file I have is only 90MB in WebM.
NOTE: Like all file conversions, a certain amount of quality loss will take place, I didn't notice any, so your best bet would be to try it out and see for yourself.