@Stephanie Leary -
We'd had the same issue with a site that used over 900 links. It finally loads in the admin, but is a mess to deal with without pagination. Oddly, the Link Categories *does* have pagination. Go figure.

I certainly wouldn't replace Links with Menus since they're quite different - so, I'm with everyone else with seeing Links pushed into Custom Post Types too... of course we'll need some converter for my site mentioned above :)