Aims: The aim of the project is to search for lithium in absorption at 6707.8 Å to constrain the nature and mass of the brightest low-metallicity L-type dwarfs (referred to as L subdwarfs) identified in large-scale surveys. Methods: We obtained low- to intermediate-resolution (R ~ 2500-9000) optical (~560-770 nm) spectra of two mid-L subdwarfs, SDSS J125637.13-022452.4 (SDSS1256; sdL3.5) and 2MASS J162620.14+392519.5 (2MASS1626; sdL4) with spectrographs on the European Southern Observatory Very Large Telescope and the Gran Telescopio de Canarias. Results: We report the presence of a feature at the nominal position of the lithium absorption doublet at 6707.8 Å in the spectrum of SDSS1256, with an equivalent width of 66 ± 27 Å at 2.4σ, which we identify as arising from a CaH molecular transition based on atmosphere models. We do not see any feature at the position of the lithium feature in the spectrum of 2MASS1626. The existence of overlapping molecular absorption sets a confusion detection limit of [Li/H] = -3 for equivalently typed L subdwarfs. We provided improved radial velocity measurements of -126±10 km s-1 and -239±12 km s-1 for SDSS1256 and 2MASS1626, respectively, as well as revised Galactic orbits. We implemented adjusting factors for the CaH molecule in combination with the NextGen atmosphere models to fit the optical spectrum of SDSS1256 in the 6200-7300 Å range. We also estimate the expected Li abundance from interstellar accretion ([Li/H] = -5), place limits on circumstellar accretion (109 g/yr), and discuss the prospects of Li searches in cooler L and T subdwarfs. Optical spectra of SDSS1256 and 2MASS 1626 are only available at the CDS via anonymous ftp to http://cdsarc.u-strasbg.fr (ftp://130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz-bin/qcat?J/A+A/579/A58Based on observations collected at the European Southern Observatory, Chile, under programmes 089.C-0883 and 091.C-0594A.Based on observations made with the Gran Telescopio Canarias (GTC), installed in the Spanish Observatorio del Roque de los Muchachos of the Instituto de Astrofísica de Canarias, in the island of La Palma (programmes GTC64_10B and GTC38_11A).