In The Legend of Zelda: Skyward Sword there is supposed to be a Sheikah Stone that sells treasure. This answer tells where to find the stone, but says nothing about when it is available. How soon can I find it?
You can only access the Moonlight Merchant toward the end of the game after you completed the Hero Song.
At this point, the monsters will leave the Waterfall Cave completely and you will find the butterflies inside at night.
The monsters only leave when you've made Batreaux human. I'm not sure about the Song of the Hero - I think you need to have received the Stone of Trials first but I'm not sure.