Specifications of the LED:
Max. Current : 750 mA
Forward voltage : 3.5 - 4.5 V Max.
Working temperature: 60 °C
These specs are not good for a battery powered LED.
3.5 - 4.5 Vf says it is a horribly inefficient LED.
When battery powered, always start with an LED with the highest efficacy possible. Today that LED is a Cree XP-G3 XPGDWT-01-0000-00ME3. High efficacy means more light and less heat. This White, 5000K Cree LED has a efficacy of 180 lm/W.
At 750 mA this LED's Vf is 2.85V. See Pg. 18 of datasheet.
Just using a resistance setup to regulate current to the LED, I know
it's not very efficient
This is not always true. You can easily power this with the Arduino UNO's 3.3V. You cannot do this with a 3.5-4.5V LED. With a 2.85V LED powered by 3.3V with a current limiting resistor would give you an efficiency of over 86% no matter what current you run at.
I'm powering the Arduino with a USB cable and the LED with 4x AA NiMh batteries
Powering a 5V Arduino with 4.5V batteries is not good. The Arduino wants at least a 5.1V input. The Arduino Vin is run through a 5V NCP1117ST50T3G LDO regulator. The minimum input voltage for the 5V NCP1117 is 4.950V.
You should just use a 5V USB power bank to power the Arduino and use the Arduino's 3.3V to power the LED. You probably cannot run it at more than 250-300 mA without a heatsink. At 250 mA the Cree Vf is 2.7V so a 2-2.4 Ω half watt resistor would give you better than 80% efficiency. Well, minus the the efficiency of Arduino's 5V and 3.3V LDOs.