late 14c., apparently just what it looks like: a fanciful name from Middle English tadde "toad" (see toad) + stole "stool" (see stool). Toads themselves were regarded as highly poisonous, and this word is "popularly restricted to poisonous or inedible fungi, as distinct from edible "mushrooms" [OED]. Compare toad-cheese, a poisonous fungi; toad's meat (1886), a "rustic" term for toadstool.

"a toad, a frog," late 14c., paddok (late 12c. as a surname), probably a diminutive of pad "toad," from Old Norse padda; from Proto-Germanic *pado- "toad" (source also of Swedish padda, Danish padde, Old Frisian and Middle Dutch padde "frog, toad," also Dutch schildpad "tortoise"), of unknown origin and with no certain cognates outside Germanic. Paddock-stool was an old name for a toadstool (mid-15c.). Pad in the straw was a 16c.-17c. expression meaning "something wrong, hidden danger."