i dont really understand the question. your picture seem contrary to your description.
your picture seems to suggest you can cut in any direction, but your description suggests all cuts have to be in the same direction.
i'll solve both.
for lines in any direction: http://mathworld.wolfram.com/CircleDivisionbyLines.html
1/2*(n^2 +n +2), n=500; 125251
5000000 = 1/2*(n^2 +n +2) n=3162
for cuts in the same direction:
each cut adds 1 new region.
for 500 cuts, that 501 rejoins
to get 5000000 peices 4999999 cuts are needed
phil1882's post in Cutting pizza was marked as the answer