Sound like you were trying to save the files too small for their resolution (and detail). It is impossible to compress for example a 22MP photo (of a detailed scene) whose jpeg right out of camera has about 10 Megabytes to 0.5 Megabytes without making it all blocky and weird looking. Even Photoshop has some minimum quality in its jpeg compression dialog (a full 22MP photo from e.g. Canon 5DmkIII usually can't get below 1MB even if you save it at Photoshop's zero quality).
In Photomechanic, if I remember correctly, when you use the Limit file size to ... dialog, the quality slider above still lets you control the
minimum quality of the photo. JPEG compression depends heavily on the detail in the original photo. A simple view of blue sky could be much smaller than a highly detailed landscape scene. There is a sweet spot between acceptable quality loss, filesize, original photo detail and resolution. JPEG compression is not magical. It can't work miracles, it won't produce a 20x smaller file with still acceptable quality of the result. Either you have the quality slider set too much to the right for the intended file size, or (if the quality is set all the way to the left), the photos are just too big and detailed to be saved at your intended file size.
If you consistently find yourself in need of saving 0.5 MB files, you should probably downsample the photos. Use Resize dialog to set a lower resolution.
Please see the manual or at least the Limiting size of JPEGs FAQ here ...
http://forums.camerabits.com/index.php?topic=7453.0