Waypoints should act as nodes, you'd have to store coordinates as well as names of waypoints it is directly connected to. So when you look for a path, you can solve through each waypoint's neighbours, iterate until you find the goal, then use the shortest path.
As for your question, multiple map pieces are better than one large map. The 4000x2000 would use up 4096x4096 pixels in video memory, which is 16 MB. If you break it down into 1024x1024 pieces, you can use eight of them, each is a megabyte, thus you save 8 MB memory. Moreover, only one of them would be rendered at a time (if you use 1024x768 resolution), so it would be faster to load and render.