We report large-scale first-principles simulations of melting of four different phases of Li at pressures ranging from 0 to 50 GPa. We find excellent agreement with existing experimental data at low pressures, and confirm that above 10 GPa the melting line develops a negative slope, in parallel to what occurs for Na at 30 GPa. Surprisingly, our results indicate that the melting temperature of the bcc phase is always higher than that of fcc Li, suggesting the intriguing possibility of the existence of a narrow field of bcc stability separating the fcc and liquid phases, as predicted by Alexander and McTague [Phys. Rev. Lett. 41, 702 (1978)].