The step up/step down regulator you linked is a switching regulator and can make good use of a battery of any voltage. The other type of regulator, a linear regulator, needs to have the battery voltage matched more closely to the regulated voltage -- preferrably ~2V above. The limitations of linear regulators is likely the source of your confusion.
So, assuming you're using a switching regulator, the best way to measure the capacity of a battery of a given voltage and Ah rating is by converting to watt-hours. As an example, your 3.7V battery with 2000mah (2Ah) capacity contains (3.7 * 2 =) 7.4 watt-hours of power. The s7v8f5 regulator suggests 90% efficiency so you'll get (.9 * 7.4 =) 6.66 watt hours of power. Converting that to 5V, you'll get (6.66 / 5 =) 1.3Ah of current, or running at .35A it would run for (1.3 / .35 =) 3.71 hours.