Clipping very large polygon datasets in ArcGIS?
As always when dealing with scalability problems, it's best to start small and simple and steadily work your way up to big and complex.
In the case of clip, it should be smart enough to deal with big datasets because it tiles them internally. But since it's not working, try running Clip with the input dataset (the data to be clipped) and the clip dataset (the data with which the clip is performed) with many, many fewer features. Like one clip feature, with only the area around it in the input dataset (use definition queries to shrink them). Make sure that it's running okay, and then steadily increase the scope of the geoprocessing operation until performance degrades.
A couple specific ideas:
Dissolve the clip features into a single, multi-part feature class.
Reduce the file size of the input features using Simplify Polygon. A 5GB vector dataset is enormous--even a shapefile of all 250,000 US Census block groups is only about 1GB.
Split the input features into parts. Theoretically the internal tiling routines within the geoprocessing tool should be doing this already, but you never know. There may be some 32-bit file size limitation issue where you can't have a shapefile bigger than 232 bytes = 4.29GB.
Some other, more general geoprocessing performance tips:
Make sure both datasets have the same coordinate system. If possible, it's faster to have both in a geographic coordinate system with no projection.
Make sure you are not running off of a network drive. Use the fastest local hard drive or, if possible, an SSD.
Load the clip dataset into memory.
Delete unnecessary attribute fields (and rejoin them later if needed).
Other geoprocessing performance tips.
Or, you could give up on ArcGIS and try doing the clip in OGR. See an explanation here. I've found this works when nothing else does!
Some ArcGIS functions like Union and Intersect use adaptive subdivision processing as described in Tiled processing of large datasets. Unfortunately it appears as though Clip does not have a large geoprocessing tool.
It seems like you might be able to replicate this concept via a ModelBuilder or Python script that uses the Split tool (ArcInfo) to help process oversized datasets.