wp_list_categories in in nav_menu

Something along these lines should at least get your started. You’ll need to register the menu first and get the ID. I didn’t get to deleting categories but you’ll need to take care of that as well.

This is largely untested. Back up your DB first!!

add_action( 'created_category', 'my_update_category_menu' );
add_action( 'delete_category ', 'my_delete_category_menu' );

function my_update_category_menu ($cat) {
    $category = get_category($cat);
    $menu_id = yourMenuIdHere; // <--------- YOUR ID

    wp_update_nav_menu_item($menu_id, 0, array(
        'menu-item-title' =>  __($category->name),
        'menu-item-classes' => $category->name,
        'menu-item-url' => home_url( get_category_link( $category->term_id ) ), 
        'menu-item-status' => 'publish')
    );

}
function my_delete_category_menu ($cat) {
    $category = get_category($cat);
    // not sure how to get the backwards look up but menu items are stored as posts 
    // http://codex.wordpress.org/Function_Reference/wp_delete_post
}

If you want to bulk add existing categories (though it’s pretty easy to do it manually via the admin) something along these lines should work. Run it once and remove it from your functions.php.

$categories = get_categories();

foreach($categories as $category) {

     wp_update_nav_menu_item($menu_id, 0, array(
        'menu-item-title' =>  __($category->name),
        'menu-item-classes' => $category->name,
        'menu-item-url' => home_url( get_category_link( $category->term_id ) ), 
        'menu-item-status' => 'publish')
    );

}