How is Carboxymethyllysine formed from the heating of olive oil?
Given that the levels are expressed in arbitrary units (based on the results of an immunoassay), it's difficult to say how much CML there actually is and accordingly, how much lysine is needed to produce it. It may be that only a small quantity of lysine is required) In fact, a different study found no CML in raw olive oil. 

CML is produced during cooking from glycation of the side chain amine, starting with the Maillard reaction between the amine and a reducing sugar's carbonyl at high temperature. However, in the paper you cited, there was already significant CML in raw olive oil that was only somewhat increased by cooking. This paper suggests that CML formation is related to the oxidation of fatty acids and found that oils with increased concentrations of unsaturated fatty acids (olive oil is in the middle of the 5 oils they tested) were more prone to forming CML, but they deliberately added lysine to test it. It could be that this oxidation is something that happens in storage and the study you linked was using old oil or something. Also, just as with any other plant derivative, there could be significant variation in lysine content from different olives. This site indicates a lysine content of 3 mg/8.3 g whole olive, so there is some there. How much actually makes it into oil, I don't know.