Easyish as long as it's a small niche market and you don't have too many products.
You will have to create (or copy) a category structure and manually match each product to your structure. After that you will have to match all the products which are the same.
The sort of problem you will discover is for an identical small spade you might get the following.
Merchant => Product id => Product =>Category
Merchant a => 123 Small Spade =>Hand Tools
Merchant b => 456 Ladies Spade =>Garden Equipment
Merchant c => 789 Ladies Small Spade =>Garden Accessories
So first you would put them all in the same category of your own.
This may be done in bulk with php initially merge the three merchants categories into the new one you created.
Now create a look-up table which would look like
1 a 123 1
1 b 456 1
1 c 789 1
Hope that helps