Since I decided this would actually be pretty damn useful for myself too, I pushed on and wrote a custom walker, Walker_Paged_Threaded.
I’ve tried to comment to the best of my ability, and admittedly it’s a little thrown together, but I’m happy with the result.
How To Use It
The class is written with the same abstract approach as the original Walker, so as not to limit it to just comments. However, to keep things simple, we’ll rename it*;
Walker_Comment_Paged_Threaded extends Walker_Comment
Now in your theme’s comments.php;
wp_list_comments( array( 'walker' => new Walker_Comment_Paged_Threaded ) );
Wahey! Paged comments that account for threading.
Known Side Affects
Since we’ve changed the way pages are calculated, functions like get_comment_pages_count will start to behave abnormally when passed parameters like $per_page or $threaded. Out-of-the-box though, this is not the case.
However, get_comment_pages_count will still fallback on Walker_Comment if $wp_query::max_num_comment_pages is empty. But providing you call wp_list_comments first, it’ll run the walker and set the property automatically.
If you are displaying comment pagination or page links before your comments, you’ll need to do something like so;
<?php
/**
* Capture comments in an output buffer. The function needs to run before
* displaying page links, as it runs the walker and then sets the
* 'max_num_comment_pages' property on $wp_query.
*/
ob_start();
wp_list_comments( array( 'walker' => new Walker_Comment_Paged_Threaded ) );
$comments_list = ob_get_clean();
?>
<?php paginate_comments_links(); ?>
<?php echo $comments_list; ?>
This is actually the neatest way to get around it, trust me!
*If you want to keep it abstract, without multiple copies for each intent, you could fake ‘multiple inheritance’, which is a little ugly.
N.B. I thought best to add this as a separate answer, as it’s actually an answer!