In 1654, one Friedrich von Logau wrote something in German that Longfellow (sometime in the 1800s) translated into English as:
Though the mills of God grind slowly, yet they grind exceeding small;
Though with patience He stands waiting, with exactness grinds He all.
The word "small" is necessary there to make the rhyme work, but I never see it quoted that way. There are a lot of variants in modern use, but almost all of them include the phrase "they grind exceeding fine." (Sometimes "exceedingly fine.") The modern use never includes the second line; presumably if it did, there'd have to be a different word at the end, to rhyme with "fine."
I'm really curious now as to where and when the change occurred. Remarkably, there's an early citation on the Web: a speech by Rep. Richard H. Cain, an African-American Representative addressing the House in 1875, includes the comment "The mills of the gods grind slowly, but surely and exceeding fine." This phrasing has become fairly common; I can't help but wonder whether it was a misquote of Longfellow (I don't know when Longfellow's translation was published) or simply a different translation of von Logau's original.
And I think it's fascinating that not only does the phrasing Cain used include "fine" and "but surely," but it uses "mills of the gods" instead of "mills of God." And in fact, many if not most modern uses of the phrase also use "of the gods."
I have no conclusion here; I just think this stuff is interesting, and I'm always startled to learn that a quotation I've known forever turns out to not originally have been stated the way I've always heard it.