The word "бай" has its roots from very old Slavic word "баять", that means "to tell stories". Nowadays this word ("баять") is not used, but the words "баю-бай", "баю-баюшки-баю" etc. remain and became just words to make children sleep. Here is a close expression: "кот-баюн", it is the cat which tells fairy-tails.