Why does Italian use Lei (feminine third-person singular) instead of lui (masculine third-person singular) in formal speech, irrespective of the sex of the addressee?
According to La Grammatica Italiana, by the Istituto Treccani
Until the fourteenth century the system of allocutive pronouns was composed only by tu and voi as a form of respect. The first attestations of lei go back to the fifteenth century and between the sixteenth and seventeenth this usage spreads gradually until it became preponderant, likely for the influence of the Spanish usted.
Fino al Trecento il sistema degli allocutivi era costituito solo dal tu e dal voi come forma di rispetto. Le prime attestazioni del lei risalgono al Quattrocento, e tra Cinquecento e Seicento questo uso si diffonde gradualmente fino a diventare preponderante, probabilmente per l’influsso dello spagnolo usted.
So it seems likely that the feminine form lei was used because usted in Spanish is feminine. Moreover usted is feminine because it is a contraction of vuestra merced, "your grace", which is feminine in Spanish (as in Italian: "vostra grazia").
§9.6 of Maiden's A Linguistic History of Italian:
Pronouns of address
The CL second person pronouns distinguished singular (TU) and plural (UOS). This system is continued in many southern Italian dialects (e.g., in Abruzzo, southern Marche, southern Puglia and parts of Campania and Calabria), but in the history of Italian (together with many other Romance dialects, among them the Italo-Romance varieties of Naples, southern Calabria, northern Puglia, Rome, Canton Ticino and Corsica), a morphological distinction has arisen, originally encoding deference towards, or respect for, the addressee, but acquiring, in more recent times, the additional function of indicating politeness, distance, or membership of a distinct social group from the speaker.79) In about the third century, second person plural forms begin to be used for singular polite or deferential address, with corresponding verb forms (but singular adjectives): the same development is observable across many of the world's languages.80) Of later date, and more restricted in its geographical extent (among Romance languages it is limited to Ibero-Romance and Italian, and is not well established in the Italo-Romance dialects, particularly those of the centre and south81), is the use of a third person pronoun, singular Lei and plural Loro. These originate in the use as forms of address of honorific nouns, rather like English ‘your honour’, ‘your worship’, ‘your ladyship’ – cf. Brown and Levinson (1987: 276f.); the language of the sixteenth century developed a profusion of honorifics such as vostra signoria; vossignoria;82) vostra eccellenza, etc. It seems that the use of such devices received a considerable impetus from Spanish models, such as Vuestra Merced (> usted) in the sixteenth century, although the employment of third person forms is detectable as early as the thirteenth (cf. Brunet (1987: 12). These (usually feminine) nouns are replaced by feminine third person pronouns, which are the source of modern Ella, Lei and plural Loro. For the use of capital letters with these forms, see Brunet (1987: 43–7). The perception that third person address forms are a product of foreign influence prompted the Fascist authorities, in the 1930s, to denounce Lei in favour of the supposedly more ‘Italian’ polite voi (see Brunet (1987: 69–78). Such denunciation served only to promote a reaction in favour of Lei in the post-Fascist period.
The stylistic differentiation between (originally nominative) Ella and (originally oblique) Lei permits a further differentiation in modern Italian, in the singular, between Lei and the strictly formal and elevated Ella. While the distinction between tu and Lei is firmly established in the singular, it is less so in the plural, where voi is still regularly directed to individuals who, singly, would be addressed as Lei. For many Italians, the use of polite Loro connotes a higher degree of formality, than does Lei (see Brunet (1987: 21f.). The clitic forms of these pronouns are La and Le, although it is not uncommon to hear lo/gli where the addressee is male. The plural form corresponding to Loro is commonly li with male addressees. Adjectives qualifying Lei normally take the gender form corresponding to the sex of the addressee, except that the past participle usually has feminine agreement with preceding direct object clitic La, particularly where the vowel is elided: e.g., L'ho vista ‘I've seen you (masculine)’, etc. For contemporary usage of the pronouns, see Brunet (1987), and Berruto (1990: 93f.).
79. For an account of the changing functions of the address forms in Romance (and elsewhere) see Brown and Gilman (1960).
80. For some reflections on its origins see Brown and Levinson (1987: 198–204).
81. It is best established among northern dialects, notably of Piedmont and the Veneto, but often with a masculine pronoun (corresponding to Italian lui), where the addressee is male. See Rohlfs (1968: 183).
82. Forms such as vussignuría, vussía continue to be available as reverential or polite forms of address in many areas of southern Italy (and also in parts of Liguria and Piedmont), although usually accompanied by a second person singular verb form.