How can I make wp_list_categories output li with category-slug as class, for its children?

I am not sure if querying the categories again is the good idea. The following code extends the Walker_Category and makes use of it to do the replacement. Put the following in your functions.php:

class WPSE67791_Walker_Category extends Walker_Category {

    public function start_el(&$output, $category, $depth, $args) {
        parent::start_el( $output, $category, $depth, $args );
                $find = 'cat-item-' . $category->term_id . '"';
                $replace="category-" . $category->slug . '"';
                $output = str_replace( $find, $replace, $output );

    }
}

Then call wp_list_categories as following:

wp_list_categories(
   array(
      'child_of' => 4,
      'walker' => new WPSE67791_Walker_Category
   )
);