Counting overlapping polygons from one Shapefile using ArcGIS Desktop?

I have a shapefile with 16,400 polygons. Each polygon shows the expansion of a bird species for the whole world.

Now I have to count the overlapping polygons. I tried it with union and dissolve (count the union), but the union is not working for so many polygons.

Then I tried to clip continents, but this is also not working because of the huge number of polygons. Moreover I tried this method , also without success.

Therefore I'm asking you I there is a way to count overlapping polygons if 16400 polygons are in one shapefile?

I'm working with 10.0 and can work with 10.2. An ArcPy solution is also wonderful.

At the moment I am thinking about creating a fishnet and iterate over the rows of the shp with the 16400 polygons and write 1 to a value field of a fishnet cell if the polygon is in this cell and than take the next row (polygon) and if this is also in the fishnet cell count +1.

But I don't know if this is a good solution and how to realize it. Or I have to learn R to use this approach.

The result: It should be a shape where you have new polygons out of the overlapping ones and a field where the overlaps are counted.

So in the end there should be a shapefile where you can see how many bird species are found at the same place.