You can play with Walker to customize output into being split by letters. From there it is matter of CSS to achieve column formatting.
Quick take on Walker:
class Walker_Alphabetized_Category extends Walker_Category {
var $letter="";
function start_el(&$output, $category, $depth, $args) {
$current_letter = strtoupper(substr($category->name,0,1));
if( empty($this->letter) ) {
$this->letter = $current_letter;
$output .= "<li>{$current_letter}<ul>";
}
elseif( $this->letter != $current_letter ) {
$output .= "</ul></li>";
$this->letter = $current_letter;
$output .= "<li>{$current_letter}<ul>";
}
parent::start_el(&$output, $category, $depth, $args);
}
}
echo '<ul>';
wp_list_categories(array(
'hierarchical' => false,
'orderby' => 'name',
'title_li' => '',
'walker' => new Walker_Alphabetized_Category(),
));
echo '</ul>';