Well, to run it sequentially you'd make a loop:
Code:
for i in *.mpg; do mencoder "$i" -o "$(basename "$i" .mpg).avi"; done
If you use different options for each video, you can just write the commands separated by colons ";" and they will execute in order. If you want to run them in parallel, just open as many terminals as you have cores and start encoding all of them at once. Or you can use the threads options and just encode one at a time.
You can try many things.