The search GET should return what you need. It would look something like this:
The response will include an object containing 4 fields -> total, start, count, and data. Data will be the array of candidates returned. The total field is what you will use for your iteration. For example if you send the search above and the total is 687, the data array will contain the first 500. Your next query would have the start parameter as 501.
What I have done in the past is to check the count value after each call. If it equals 500, I make another call. If its less than 500 I know I'm done.