Adding category ID or slug to WP Nav Menu

Use the nav_menu_css_class filter to add classes to wp_nav_menu output.

Add ID (no additional query needed):

function wpa_category_nav_class( $classes, $item ){
    if( 'category' == $item->object ){
        $classes[] = 'menu-category-' . $item->object_id;
    }
    return $classes;
}
add_filter( 'nav_menu_css_class', 'wpa_category_nav_class', 10, 2 );

Add slug (loads category object via get_category):

function wpa_category_nav_class( $classes, $item ){
    if( 'category' == $item->object ){
        $category = get_category( $item->object_id );
        $classes[] = 'menu-' . $category->slug;
    }
    return $classes;
}
add_filter( 'nav_menu_css_class', 'wpa_category_nav_class', 10, 2 );