How to apply next/previous classes to LIs for pagination links?

Happy to say that it’s not hard at all to achieve what you are looking for.

As I understand it, you have to add a call to wp_paginate() in (one of) your theme(s) template file(s) when using this plugin, and that call looks something like this:

<?php if(function_exists('wp_paginate')) {
  wp_paginate();
} ?>

To do what you need just create your own function, let’s call it mysite_paginate() and call it instead of the code above.

Within your function mysite_paginate() call ob_start() to start output buffering, then call wp_paginate(), and then call ob_get_clean() to capture the output created by wp_paginate(). The final step is to then use a regular expression search and replace with preg_replace() to add the classes you want and then echo the results to the browser.

The code you need is below. You can add it to your theme’s functions.php file or in a .php file of a plugin you may be writing:

function mysite_paginate() {
  if(function_exists('wp_paginate')) {
    ob_start();
    wp_paginate();
    $html = ob_get_clean();
    $html = preg_replace('#<li>(<a href="https://wordpress.stackexchange.com/questions/7443/[^"]+" class="next">)#Us',
              '<li class="next">$1',$html);
    $html = preg_replace('#<li>(<a href="https://wordpress.stackexchange.com/questions/7443/[^"]+" class="prev">)#Us',
              '<li class="prev">$1',$html);
    echo $html;
  }
}

And if all goes as planned, this is what you should expect to see when using an element inspector with your browser:

Screenshot showing classes added to the HTML output of WordPress