Assuming there are no issues with hardware, I would look into MySQL settings such as max clients. Not sure what is optimum for Magento (memory requirement per process). But Apache will keep forking processes until it either hits the max client limit or until it runs out of RAM. After that it will start thrashing the disks.
Like all big CMSes Magento relies heavily on cache for performance. What kinds of cache is in use (other than MySQL)? Optimally you want to be caching at every layer not just MySQL. Turn on OpCode cache in php to cache previously parsed php code. Then look into turning on or installing an object cache layer for MySQL queries. Here you could implement APCu, Redis, or Memecache (or APC if pre php 5.5).
For even faster results add Varnish in from of the CMS to cache whole pages statically.