My new algorithm now uses some swanky computational geometry to calculate the enclosed area. It took a bit of scribbling on a paper pad to get this right. Some notes:

1. If you naively use the coordinates you land on as the points of a polygon and then calculate the area of that polygon, you will slightly underestimate the enclosed area.
2. The error comes from the contribution of the area of the perimeter. Drawing out the sample case and observing how it contributes, it basically contributes 1/2 m^3 for every straight portion of the perimeter, and 1/4 or 3/4 for a corner, depending on if that corner is a right or left turn. It should instead contribute 1 for each perimeter tile, so you need to calculate this difference.
3. You can use the cross product to determine if a set of 3 points forms a straight line, a left turn, or a right turn.

So, here's what I did. I looked at some old lecture notes I had on programming competition computation geometry implementation details. I copied and pasted some code that implemented a counter-clockwise check and one that calculated the area of a simple polygon. That's pretty much all I needed.

Now my code runs in a few milliseconds.

There is almost definitely a more elegant way to do what I did for this iteration but I'm happy to leave that to someone else to figure out (or copy paste from reddit or something).