You can specify the parallel processing factor in the Mosaic environment settings (See attached image), which is new to ArcGIS 10.1 SP1. However, be cautious with this method since ESRI's documentation is very minimal and bordering on cryptic. I would do some timed runs (and share your findings here) before implementing these environment settings on very large datasets. Essentially, you can set the number of cores across which the tool spreads its operation. For example, if your machine has 4 cores and you specify "50%", the process will run on 2 cores, and so on. Again, a word of caution, as this may or may not optimize the processing--I've seen examples of both.
Regarding the edge errors, I have encountered the same problem when working within a file geodatabase (FGDB). I now primarily do raster processing outside of the FGDB and make sure the output results are .img files, as these tend to be a proven and reliable format.