Old English los "ruin, destruction," from Proto-Germanic *lausa- (from PIE root *leu- "to loosen, divide, cut apart"), with an etymological sense of "dissolution." But this seems scarcely to have survived in Middle English, and the modern word, with a weaker sense, "failure to hold, keep, or preserve what was in one's possession; failure to gain or win," probably evolved 14c. from lost, the past participle of lose.
Phrase at a loss "confused, uncertain" (1590s) is a phrase from hunting, in reference to hounds losing the scent. To cut (one's) losses is from 1885, originally in finance. The retailer's loss-leader "advertised product sold at cost or below" (to entice customers in to buy other things as well) is from 1922.