Low MIPS Video Encoder
Your first problem is memory - even the largest version of that processor doesn't have that much internal SRAM (in video terms - it's a stonking embedded processor compared to many though!) - a VGA frame is 300kB, vs the 100ishkB in the processor.  That means you'll have to process it as it comes in - say in 8 or 16 line chunks, which makes it much more of a "hard-realtime" problem as the deadlines have less slack in them.

It's not clear how you'll be capturing data, but I assume that you'll have some sort of DMA from either the ADC or some digital port, otherwise you'll be spending half your time shuffling data around! 

Aiming for lowish compression ratios, you might just want to look at encoding the deltas between pixels along a line or a 3x3 square and then arithmetic code them.  

See also Simple, streaming, lossless image compression - although I was asking for explicitly lossless compression, there may be some ideas for you there.

As a datapoint, one of my colleagues implemented a 320x240 8-bit mono JPG compression in a 60MHz 32-bit micro with floating point unit and a small cache.  He used some reference code (ie optimised for readability, not performance) and got 5 fps fairly easily.  Compression ratios were of the order of 10x IIRC. The image capture was done by external hardware bus-mastering the data into the micro's external RAM.