I can't promise that our techniques are state-of-the-art, but they gave us the level of confidence we needed and might give you some ideas for an approach.
We made a backup of the production database before we made the fix, with all of its known duplications. We then ran the de-duping code against that database and analyzed the duplications it found to ensure they were true dupes, and verified that it was finding all of the known actual dupes.
In addition, we created regression E2E test cases that would populate a clean database with data that covered as much of our de-duping logic as we had time to test, and then would query the database after the service was done running to verify that only the expected data remained. We already had code available to set up clean databases automatically and call the services, then run the queries and log the results; if we hadn't been able to leverage these tools, we might have used a different approach.
For performance and scalability, we timed the de-duping program running against the backup of our existing database in staging while forwarding current production traffic to the staging server to determine how many records per second were being de-duped while dealing with a standard load. We were mostly concerned with (a) if de-duping would affect the processing current traffic, and (b) how long the de-duping logic would take to catch up with current traffic. If we needed a reproducible performance test, I think we would have written a simulator program that would drop files on a pre-programmed schedule to simulate production traffic.
