Generate 64 bit HMAC
Key and tag lengths matter independently. A short tag allows a random guess to be valid more often, but does not help an attacker in finding the key. Rather than XOR, NIST recommends truncation if you need a shorter MAC tag. SP 800-107 (pdf) says to use at least 32 bits:


  When an application truncates the HMAC output to generate a MacTag to a desired length, λ, the λ left-most bits of the HMAC output shall be used as the MacTag. However, the output length, λ, shall be no less than 32 bits.


However, using at least 64 bits is recommended:


  A commonly acceptable length for the MacTag is 64 bits; MacTags with lengths shorter than 64 bits are discouraged. 


Other than that, I would not use HMAC-MD5, although it has not been broken. HMAC-SHA256 (or HMAC-SHA512 if that is faster) can be truncated to the same size.