Our old system did it by having a select list with other products you could choose to upsell at Checkout. Unfortunately that's not a good option for a site with a lot of products.

There are two things mentioned here: Related Products and Recommendations.

The main differences, IMO, are that Related products can be things in a similar vocabulary or category, while Recommended (or "Other users bought these ...") might not be related at all, although they could be for instance an accessory to the item you're buying. In that way they might still technically be related.

I'm not 100% certain you can do it with views, but I would propose a module that looks at the items in a user's cart, does a fuzzy search based on those items and the text, title, and other keywords within the product's node. Then, I would also look to see what items are in that taxonomy vocab and see how they relate to the search. This could be similar to the way the views_fastsearch works, with the exposed taxonomy etc., and then based on relevance, show the related products.

Something like Amazon's "65% of customers bought this item, others bought this item.." might be a bit more complex to do...

This is something I wouldn't mind having on the site either, and anything that can dynamically generate relevance (or even based on actual sales, although that might be a large, complicated query) would get my help. Let me know.