An intelligent animal, say, a dog, chimp, or dolphin. Could Spock meld with such creatures? What about tribbles? Humanoid beings with seemingly small amounts of intelligence, such as the Taurean creatures ("Galileo Seven"), or the Mugato?
There are definitely some examples where he mind melds with non-humanoid aliens or other beings.
One example I immediately remembered from TOS would be the episode The Changeling, where he's trying to mind-meld with the rogue probe Nomad. It obviously works.
I think there are also a few examples during Voyager, where Tuvok mind melds with sentient but non-humanoid creates in a few cases, but I can't pin any example down right now.