Edit the markup of categories list

List of possibilities

You got exactly two options to alter the output of wp_list_categories()

1. Use a filter after the MarkUp was generated and re-format it:

   add_filter( 'wp_list_categories', 'wpse88292_reformat_list_cats', 10, 2 );
   function wpse88292_reformat_list_cats( $output, $args )
   {
       // Reformat `$output` here
       // You can use `$args` to only this when condition X == Y
   
       return $output;
   }
   

2. Use a custom walker

   class Walker_Reformated_Category extends Walker_Category
   {
       static $counter = 0;
   
       function start_el( &$output, $category, $depth, $args )
       {
           if ( 'list' != $args['style'] )
               return;
   
           // Count up before doing anything
           self::$counter++;
   
           // Do additional formatting of `$output`in here
           // It's passed by reference(!)
   
           if ( 0 === self::$counter %2 )
               $output = "<div class="class-{$counter}">{$output}";
       }
   
       function end_el( &$output, $page, $depth, $args )
       {
           if ( 'list' != $args['style'] )
               return;
   
           // Do additional formatting of `$output`in here
           // It's passed by reference(!)
   
           // Don't count at the end of the el!
           if ( 0 === self::$counter %2 )
               $output = "{$output}</div>";
       }
   }
   
   # Call the categories list with your walker
   wp_list_categories( array(
       // ... some args
       'walker' => new Walker_Reformated_Category()
       // ... even more args
   ) );