The plastic in those cheap battery holders melts if just look at them in the wrong way. The secret is speed - make a decent mechanical connection between the wire and the lug, tin the soldering iron bit well and go in really fast with some fresh solder. Aim to make the joint in less than a second with minimum mechanical pressure.
If possible, get holders with wires pre-crimped.
P.S. As far as I can see, there is no 'correct' bit - the plastic just melts at a lower temperature than the solder.