"Critters of Moria"

[Lalwendë]

"Far, far below the deepest delvings of the Dwarves, the world is gnawed by nameless things. Even Sauron knows them not. They are older than he."

That's an interesting quote. Sauron was created at the beginning, and these creatures are older than him? So there are some creatures/beings potentially older than the Ainur? How do they fit with Eru then?