You would definitely want to do it leveraging groups as @DavidReed has pointed out. If there's any way you can add more granularity by breaking things into smaller groups first where there might be movement of users, that would likely be advantageous.
More than anything, because the entire sharing table gets recalculated when you have large numbers of records involved, it would still be wise to do this asynchronously. Remember that there will be a cascade effect as any kind of object sharing or group sharing record change trickles down between different group level records. With the volume of records you're talking about, using groups will be far more efficient than sharing records on an individual user basis.