If I have 35,000 new contacts in Salesforce that are not in MailChimp, should I expect 35k API calls for the initial sync?
Not at all. Only 70 API calls are needed to Salesforce (500 records per-call)
After that, I’m assuming the emails are cached and the stated 200/500 records per API call takes effect?
Yes, that is correct.
If I add another 5,000 contacts in addition to the existing 35k that have already been sync’d, should I expect another 5k API calls to have the new contacts sync’d?
No. As in the above calculation only 10 API calls would be needed.
If my entire database is sync’d and nothing changes (no new campaigns, responses, etc), how many API calls should I expect when I run a sync?
Only 1 API call will be needed in this use case.
Please note that the above API calls are for getting contacts/lists only. We also need a few API calls to retrieve fields details. We also need 1 API call for each unsubscribed members in MailChimp to update opt-out status in Salesforce.
Please also note that the above use case is applicable for one way sync as you specified (Do not sync new contacts is checked).
If you don't check that option the API calls needed would be added up based on the following:
* Number of email addresses in MailChimp that are not cached yet x 2 (search in Leads and Contacts)
* API calls to create records in Salesforce if email does not exist.