Inserting a shortcode into a genesis menu?

The problem is the fact that you are trying to echo something into a string, echo should only be used to output something, so simply change the following line:

$items .= '<li class="myclass">' . echo do_shortcode('[shopping_cart]') . '</li>';

To this:

$items .= '<li class="myclass">' . do_shortcode('[shopping_cart]') . '</li>';

Edit: On another note, this is merely a PHP question, such questions should be asked at StackOverflow.

Edit 2: In regards to your last edit on your question, shortcode functions need to return data, not echo it, this is what is causing the issue. You would need to take everything you are echoing and put it into a variable instead, and then return that variable (which contains the HTML code you want to output).

/**
 * Short code for displaying shopping cart including the number of items in the cart and links to view cart and checkout
 */
public function shoppingCart( $attrs ) {

    $cartPage = get_page_by_path( 'store/cart' );
    $checkoutPage = get_page_by_path( 'store/checkout' );
    $cart = Cart66Session::get( 'Cart66Cart' );

    if( is_object( $cart ) && $cart->countItems() ) {

        $buffer="<div id="Cart66scCartContents" style="float:right; text-align: right;">";
        $buffer .= '<a id="Cart66scCartLink" href="' . get_permalink( $cartPage->ID ) . '">';
        $buffer .= '<span id="Cart66scCartCount">' . $cart->countItems() . '</span>';
        $buffer .= '<span id="Cart66scCartCountText">' . $cart->countItems() > 1 ? ' items' : ' item' . '</span> ';
        $buffer .= '<span id="Cart66scCartCountDash">&ndash;</span>';
        $buffer .= '<!-- <span id="Cart66scCartPrice">' . CART66_CURRENCY_SYMBOL.number_format($cart->getSubTotal() - $cart->getDiscountAmount(), 2).'</span></a> -->';
        $buffer .= '<a id="Cart66scViewCart" href="' . get_permalink( $cartPage->ID ) . '">View Cart</a>';
        $buffer .= '<span id="Cart66scLinkSeparator"> | </span>';
        $buffer .= '<a id="Cart66scCheckout" href="' . get_permalink( $checkoutPage->ID ) . '">Check out</a>';
        $buffer .= '</div>';
        return $buffer;

    } else {

        $emptyMessage = isset( $attrs['empty_msg'] ) ? $attrs['empty_msg'] : 'Your cart is empty';
        return "<p id=\"Cart66scEmptyMessage\" style=\"float:right; text-align: right;\">" . $emptyMessage . "</p>";

    }

}​