How to use drupal_add_tabledrag() with paging feature?
This can be done. If taxonomy module does it then its doable isn't it? So to do that you have to mainly follow 2 functions. 


function taxonomy_overview_terms(..) in line # 249 @ /modules/taxonomy/taxonomy.admin.inc
function theme_taxonomy_overview_terms(..) in line 548 @ /modules/taxonomy/taxonomy.admin.inc.


The first function is the form that generates the list of items present in the term listing page. (The screenshot you attached)
The second function is the hook_theme implementation of the prior function and adds the table drag functionality to the page. If you look closely, the form has navigational steps added in it and then in the theme function they are made available for JavaScript to handle the back and forth navigation you mentioned. These are $form['#back_step'] &amp; $form['#forward_step']. Those are converted to backStep &amp; forwardStep and added to Drupal's JavaScript settings. So also you have to look at the taxonomy.js in where these are called and handled.