How to add a large number of overlays efficiently?

I don't think anything would render that efficiently. And you are just talking about the number of polygons. How complex is each polygon?

There are two issues to consider. One is the complexity of each polygon. You may need to simplify before rendering. You should consider what the visible size of each pixel on the screen is going to be. How much effort do you put into rendering objects that might never leave the confines of a single pixel?

Generally, you want to simplify large polygons and aggregate small ones. That way, many small polygons will just be drawn as points, or even better, some larger indicator with a badge showing the number of objects that the badge represents.

You could improve performance by not drawing anything below a given zoomScale.

Subclass MKPolygonRenderer like so:

- (void)drawMapRect:(MKMapRect)mapRect zoomScale:(MKZoomScale)zoomScale inContext:(CGContextRef)context
{
  if (zoomScale > _maxZoom)
     [super drawMapRect:mapRect zoomScale:zoomScale inContext:context]
}