It depends how different from human hemoglobin it can be and still count as hemoglobin. Here is a cool evolutionary tree of globins.
http://www.mhhe.com/biosci/genbio/enger/student/olc/art_quizzes/genbiomedia/0329.jpg
Here is the worlds smallest fish. Fish have hemoglobin similar to that of humans.
from Wikipedia: The world's smallest fish is Paedocypris progenetica1 from Indonesia, with mature females measuring 7.9 mm (0.31 in).

But I think bloodworms are even smaller. They have hemoglobin too. It is evolutionarily more distant from us but they use it for the same reason we do.
from https://www.prestoninnovations.com/img/media/Seq-7.jpg
http://www.allaboutworms.com/the-basics-of-blood-worms
Blood worms are red because their blood plasma contains haemoglobin,
like human blood. Also spelled “hemoglobin,” haemoglobin increases its
ability to take up oxygen. The larvae commonly burrow in the
oxygen-poor mud bottom of pools and rivers, so haemoglobin is of great
value to the larvae.
If you are going to allow very distant relatives, I think this snail is even smaller than the smallest bloodworm. Less than 1 mm. Molluscs have hemoglobin too.
from https://www.slideshare.net/fmoretzsohn/texas-seashellsmore-than-you