Probably the earliest usage of a similar phrase occurs in the epic Greek poem, The Iliad by Homer. In Book 21, Achilles slays Lykaon, a son of Priam, and throws him in a river. Achilles taunts him as he dies, saying "Lie there now among the fish..." (Lattimore translation) or, "Make your bed with the fishes now..." (Fagles translation). In other words, sleep with the fishes.
A similar usage can also be found in Herman Melville's Moby Dick, wherein the second mate Stubb soliloquizes: "when Aquarius, or the Water-bearer, pours out his whole deluge and drowns us; and to wind up with Pisces, or the Fishes, we sleep." (Melville, Moby Dick, ch. 94).