In Michigan, a Republican in a local election went from barely losing to winning clearly after picking up ~1200 votes in a recount. That seems like a lot to me, which got me wondering. What is the most a vote has changed as a result of a recount?
Ballotpedia has an article on Noteworthy recounts in the United States. For 2000-2015, they cite a report from FairVote:
From 2000 to 2015, there were 27 recounts in [4,687] statewide races across the country. Of those 27, there were three that resulted in a change of the election result. The average vote shift across all 27 recounts was 282 votes, which accounted for 0.019 percent of the vote in those races
That page also has a section on "Notable recounts" from a few different years (including the 2000 Bush/Gore recount). The biggest swing they have listed is the 2018 Florida Senate race, where the Republican challenger's vote lead decreased from ~15,000 votes to ~10,000 votes after both machine and hand recounts. Notably, this change in votes is larger than that of the three races where the result actually changed, because they were all closer than this to begin with.
It's certainly possible that there have been larger recount swings before 2000, or in single-district races which FairVote didn't look at, but it's unlikely that anything smaller than a state-wide election had a vote shift larger than that 5000 vote Senate one, simply because of the smaller number of votes involved.