"place where something is discarded," by 1921 (in phrase give (something) the deep six), originally in motorboating slang, perhaps from earlier underworld noun sense of "the grave" (1929), which is perhaps a reference to the usual grave depth of six feet. But the phrase (in common with mark twain) also figured in sailing jargon, of sounding, for a measure of six fathoms:
As the water deepened under her keel the boyish voice rang out from the chains: "By the mark five--and a quarter less six--by the deep six--and a half seven--by the deep eight--and a quarter eight." ["Learning the Road to Sea," in "Outing" magazine, Feb. 1918]
In general use by 1940s. As a verb from 1953.