Niel de Beaudrap's answer has discussed the fact that there is no logical negation going on. A separate issue is that "infinitesimally small" can be applied not just to a number but instead to a thing to be measured, and small versus large size is only one type of measurement. For example, a banker's heart could be infinitesimally small, a socialite's infinitesimally heavy. The former says you'd need a microscope to see it. The latter says that she spent an entire 7 seconds today pondering the plight of Romanian orphans. Things can be infinitesimally important, infinitesimally valuable, and so on.
In a purely mathematical context, there is a longstanding tradition of describing things by their measure. For example, Euclid says that a certain triangle and a certain square are equal, meaning that their areas are equal. If we feel that this blurs distinctions, then we can use a word such as "small" that clarifies that we consider the two shapes equally small in measure, not equal in the sense of being congruent or constituting the same point-sets.
Since one answer has claimed that "infinitesimally small" is a pleonasm, here's an example that wasn't written by ignorant people or for ignorant readers:
Only for an infinitesimally small region of four-dimensional space,
i.e., for one in which the potentials g_μν can be considered a
constant -- is 'velocity' defined at all.
--Janssen et al., The Genesis of General Relativity, p. 403. This is a good example of the use of "small" to clarify the meaning. Suppose the authors had written simply:
Only for an infinitesimal region is 'velocity' defined at all.
That would have left us wondering what measurement they had in mind for the region that would make its measure infinitesimal.
Googling for examples of "infinitesimally small," I also noticed that the phrase can come up in translation.
Cette difficulté peut être levée en supposant la différence de température entre le corps A et le corps B infiniment petite[...]
--Carnot, Reflexions sur la puissance motrice du feu, p. 27. Some translators render "infiniment petite" as "infinitesimally small," when "infinitely small" would have been more literal, and "infinitesimal" more idiomatic.
An argument against "infinitely small" is that "infinitely" doesn't literally mean "very, very," it means "enendingly." If a road is infinitely long, it means that you can walk on it for as long as you like, but you won't reach the end. That doesn't quite logically make sense when you apply it to something very, very small -- a small thing isn't "unendingly small" (which is what infiniment petite means).