mEdvEd71

Нужно для начала получить метки массивом, для этого поменяйте параметр "format" на "array"

$items = wp_tag_cloud($args);
$array = array();
foreach( $items as $item ){
     $letter = mb_substr( $item, 0, 1 );  //обрезаем первую букву метки
     $array[$letter][] = $item;
}

Теперь получается что в массиве идет разбиение по первой букве метки.
Можно циклом выводить так как нужно.

ob_start();
foreach( $array as $l => $i ){
    echo $l;
    foreach( $i as $item ){
         echo $item; //тут список меток на букву.
    }
}
return ob_get_clean();

Я таким образом разбивал города по буквам, возможно есть вариант лучше.