I know this is usually, 99.999999% of the time, a big NO NO but seeing as you are On-Premises, this would be one of the few times that I would take the big stick directly updating the SQL database.
Backup everything then do it with a SQL Update statement.
There is a faster way, however it may not accomplish your end goal. The likely culprit that is making this run so slow is that each update of the record triggers the Marketo Plug-in to run and evaluate the new field to determine if it should synch the record. If you turn off the plug-ins (plug-in registration tool to disable to SDK message processing step for update) then it will likely run significantly faster however if the end goal is to have specific records synched to Marketo then disabling the plug-in will thwart that goal. If however you discover that out of the 3.5mm records that 2.4mm should be set to NO synch and only 1.1mm to YES – then I would turn off the plug-in, run the Kingswaysoft job to update all the records that should be NO to NO, then turn back on the plug-ins and update the records that should be YES to YES. You are doing a one-time effort here to get your marketing engine up and running, so you may want to split up the work so that it goes the quickest way possible. Generally on work like this I would only consider shutting off plug-in execution over a weekend when activity is expected to be low from end users and the updates aren't likely to have a negative impact to their productivity.
If you've found this thread useful, dive deeper into User Group community content by role