Run the following two SQL commands from PHPMyAdmin to clean up the wp_commentmeta table in your WordPress installation.
Warning: Remember, as always, to backup up your WordPress database beforehand.
This command will delete entries which have no related entry in the main wp_comments table. Apart from old comments, this also includes left over meta data from deleted blog posts.
DELETE FROM wp_commentmeta WHERE comment_id NOT IN (SELECT comment_id FROM wp_comments);
If you have the Akismet plugin installed, wp_commentmeta might be one of the largest table in your database. This table contains every single comment made on your blog, this even includes automated spam comments. These comments are preserved even if you delete them from your WP dashboard and from the wp_comments table for statistical purposes. If you have no use of that, run this command to further trim down your database:
DELETE FROM wp_commentmeta WHERE meta_key LIKE '%akismet%';