Can a CRLH based metamaterial antenna have negative gain.

I have designed a MTM antenna and it has a gain of -9dB. Is it ok or should i change the structure..?

Any antenna with a gain less than 0 dBi has efficiency problems. But, it depends what you need, of course. If your goal is to make it electrically small, then -9dBi might be acceptable.

How do you define an electrically small antenna ? I want some clarity on its size. I have read that any antenna whose dimensions are less than Lambda/10 are called ESAs. Is the size specified the length or is it the width or does it indicate something else.?

Lambda/10 works, sure. There is no formal IEEE definition as far as I'm aware.

The "size" is usually considered to be the radius of the smallest possible sphere that encloses the entire antenna.