How can I accurately estimate the power consumption of a GPS tracking device?
This is all fairly rough but based on your numbers and some past experience:


40 mA for the GPS receiver is probably a good figure to use for a start, although for most GPS receivers the maximum current is running at the maximum update rate which looks like 5 Hz for that module. You can probably save some power by setting it for a slower update rate even though you might still want the update rate to be higher than the transmission rate to capture maximum speeds for example.
You'll probably find the GSM module may spend about five seconds in transmit mode per minute or say 12% of it's time at 200 mA which would give an extra 24 mA on average. Maybe round that up and say the GSM module will take 50 mA. GSM modules are always a little trickier because it can also depend on how many retries are required and the transmit power needed to reach the basestation.
One problem I see is that page you've linked says while running an Arduino Uno the current is 46.5 mA without a load, the I/O current limit 0f 40 mA isn't related to that so you need to add on that current required by the Arduino itself. But the Nano is simpler and after a quick look at the schematic 20 mA would probably be closer the mark.


So I'd estimate as 40  + 50 + 20 = 115 mA but don't forget to take into account any conversion losses if somewhere along the line you're using a switching converter for the power supply. It's probably better for a prototype to add in say a 50% extra margin and then do some actual testing on current draw. If you don't have much in the way of test equipment just using a battery of a fairly known capacity should give you a good idea.