If every method does not work (Select by location, Clip, Intersect, etc), You might have to first break the 15 million record shapefile into 2, 3, or 4 separate shapefiles. Then, do a Select by Location and once you have the subsets selected by location, you can append the outputs all back together using the Append GP tool.