GEE 'featureCollection.union()' keeps failing

The fundamental problems here are that

• WDPA is a large collection of complex polygons.
• Computing unions gets more expensive as geometry gets more complex.
• Any single Geometry value in Earth Engine must fit in memory (whereas a feature collection can often be processed one item at a time).

The first thing that came to mind for a way to simplify this operation is that if one of the feature collections involved contained only non-overlapping polygons, then it would be possible to map over that collection and compute the area of each feature's intersection with the other collection. However, neither of the collections in your case meets that criterion.

My next idea is to do the entire computation in image space: that is, paint the features into images, and count the overlapping pixels in the images. The advantage of this computation strategy is that it need only consider the geometry of each feature (as it intersects with a region of pixels being computed) in isolation — not to compute any geometric unions or intersections.

// Puffin range
var puffinRange = ee.FeatureCollection('users/rasenior/temp/puffin');
Map.addLayer(puffinRange,{color:'blue'},'original', false);

// Range bounding box
var bbox = ee.Feature(puffinRange.union().first()).bounds().geometry();
print(bbox, bbox.area(ee.ErrorMargin(2000, 'meters')));

// Import PA polygons
var wdpaColl = ee.FeatureCollection('WCMC/WDPA/current/polygons')
  // Filter bounds to species range
  .filterBounds(bbox.geometry())
  // Filter status
  .filter(ee.Filter.inList('STATUS', ['Designated', 'Proposed']))
  // Exlude UNESCO Man and Biosphere reserves because these include 
  // buffer and transition areas which do not meet the IUCN definition of protected areas.
  .filter(ee.Filter.neq('DESIG_ENG', 'UNESCO-MAB Biosphere Reserve'))
  // Exclude 100% marine reserves
  .filter(ee.Filter.neq('MARINE', '2'));

// Set up images

var protectedAreaImage = ee.Image.constant(0).paint(wdpaColl, 1);
var puffinRangeImage = ee.Image.constant(0).paint(puffinRange, 1);

// Boolean operation: resulting image is 1 where inputs are 1.
var protectedPuffinRanges = protectedAreaImage.and(puffinRangeImage);

// Display images

Map.addLayer(protectedAreaImage.selfMask(), {palette: ['green']}, 'Protected Areas');
Map.addLayer(puffinRangeImage.selfMask(), {palette: ['blue']}, 'Puffin Ranges');
Map.addLayer(protectedPuffinRanges.selfMask(), {palette: ['#00FFFF']}, 'Intersection');

// Compute area

// We must multiply by the area of pixels to get a value that's a geometric area
// rather than a pixel count.
var rangePA = protectedPuffinRanges.multiply(ee.Image.pixelArea()).reduceRegion({
  reducer: ee.Reducer.sum(),
  geometry: bbox,
  crs: /* TODO: something needs to go here */,
  scale: 1000,  // Sampling resolution in meters at the projection's origin
});

// Export the results
Export.table.toDrive({
  collection: ee.FeatureCollection(ee.Feature(null, {'rangePA':rangePA})),
  description: 'puffinPA',
  fileFormat: 'CSV'
});

There's one remaining missing piece, without which this won't work: you need to specify a crs (projection) in the reduceRegion — this is the projection in which the images are computed, or in other words the grid with which the geometries are sampled. This affects the accuracy of the result, so ideally you want a projection which is reasonably “undistorted” over the entire region, but your region is very large in longitude and latitude, and I'm not aware of what would be best for this particular situation. it might also depend on which areas you care about the most accuracy in.