The GM862 is designed to run straight from a Li-Ion battery, like a cell phone battery. There is a battery charger for a Li-Ion battery built into the GM862.
Otherwise, the data sheet for the GE862 shows a typical voltage regulator. If your batteries are NiMh, then they will only be at about 1.2 V most of the time, so the efficiency of a linear regulator set to 4 V will be 80%. Beating that with a switching regulator will be difficult or impossible.
GSM modules are very very hard to power correctly, as they take stupidly large current peaks that start and end very quickly. Your regulator needs to supply 2 A peaks, and if you have a switching regulator that can supply that, it probably won't be very efficient at the 20 mA on standby that the module takes. If you are only sending one text and hour, the vast majority of the battery drain will be from the standby current. That means that the quiescent current is probably the most important feature, so it all points to using a linear regulator.