In fact the number of solutions of \(y^2 + y = x^3 + x \) in the field with 2n elements is
$$ 2^n - (-1 + i)^n - (-1 - i)^n $$
explaining the oscillations we saw in the chart.
Notice that
$$ |-1 + i| = |-i - i| = \sqrt{2} $$
so the magnitude of the oscillating correction terms grows like 2n/2.