It turns out you need to have visual studios 2013 installed (express or pro, but 2012 pro does not work), despite that being mentioned literally nowhere on the packaging page Packaging Unreal Engine Projects | Unreal Engine 5.1 Documentation
Would be nice if someone could add that to reduce some confusion.