How to efficiently boost a low voltage high current input to a high voltage low current output
The most efficient solution widely available to convert a voltage into a higher voltage is a Boost Converter.

A Boost converter is efficient because it is a DC-DC Power Converter. Other methods such as charge pumps are typically voltage converters. The distinction is important because by transferring power from the input to the output it's theoretically (but not practically), 100% efficient. 

Going by your numbers and a 100% efficiency your 6V, 500mA (3W) output would draw 3W from the input (i.e. 3.7V, 811mA).

More practically, a 90% efficiency gives an input power of 3W/0.9 = 3.33W = 3.7V, 900mA