My big Danish dictionary translates 'lilla' as lilac, mauve - but not purple. Going the other way, it translates purple as 'blåligrød' or 'lilla' or 'rødviolet' - so I think you should allow 'They have lilac shoes'! (It's confusing in English, too!)
I don't know about allow it but that is certainly how I will remember purple is lilla. I try where possible to use mnemonic devices which translate or approximate the word in to my native tongue :)
That's distinguishing moment. There is no plural marker, but "shoe" is wrong
If there's no article on a countable word in this kind of sentence then it's safe to assume it's plural. There is no plural indefinite article, much like English but one would be required if it was singular.
De har en lilla sko = They have a purple shoe
De har lilla sko = They have purple shoes
"They have purple shoe" doesn't make sense.
Apparently it is one of these words like in English "jeans" it can be both singular and plural. But that's just my guess...