Even without the common story that it’s flutterby anagrammed, there have been many suggestions, and a lot are at least somewhat interesting.

One suggestion is that it’s about the color of certain butterfly species, like the brimstone butterfly. Another suggestion says that it reflects a belief that butterflies excrete butter, as per Middle Dutch boterschijte, or a reflection of the belief that butterflies eat milk and butter like with the old German words Botterlicker, Milchdieb and Molkendieb.

As an aside, the German term Falter is from Proto Germanic fifaldo, probably from reduplication of PIE pel “feel, shake”, which connects it with papilio of Latin and fiðrildi of Icelandic.