Hi Karl Wright,
I was thinking in the limitation of convexity for circle planes and I worked out another approach that overcome this limitation. There is a condition, circle lanes must contain the center of the circle which is probably always true for planets like WGS84 which are not too far from the sphere.
The idea is create a short of polygon for every slice using the center of the circle (like an orange) and therefore you can treat them separately. I attached what I developed, it seems to pass all tests regardless of the radius.
Let me know what you think and if I am missing something.