glDeleteTextures does not remove picture from memory

What do you mean with "nothing happens", how do you observe that "nothing happens" and what do you expect to happen?

In Instruments I do not see any memory drop.
Even if I remove a lot of textures.

Maybe it is because I use automatic reference counting.

Strictly speaking, the specification only says that, after deleting a texture object, the object is considered unused. It says nothing that internal resources has to be released. It is possible that internal resources are saved for future textures. If Instruments doesn't inspect the internal states of the OpenGL implementation, it is likely that it cannot differentiate between objects and internal resources.

The only way to determine if the texture is valid is to query the object handle with glIsTexture. But this does not reflect any internal resources which may be what Instruments is reporting.

well there is one thing you should try
I assume that you are probably deleting textures in dealloc method...
You should check if you still have working context (this is very important because otherwise you don't have working connection ) and delete textures before releasing context

"OpenGL functions do not work unless an OpenGL context has been created and is active within that thread. Thus, glGenTextures will do nothing before context creation, and glDeleteTextures will do nothing after context destruction."

for more info you should check http://www.opengl.org/wiki/Common_Mistakes part the object oriented Language problem

This is normal behaviour and is nothing to be worried about. The GL spec just specifies that the texture name is free for reuse and that the texture object has neither contents nor dimensionality. It says nothing whatsoever about the memory used for the object. GL implementations are free to keep the memory hanging around for subsequent reuse if necessary, to free it some arbitrary time later, or whatever the driver writer decides is the best behaviour.

Don't expect a glDeleteTextures call to behave like free () or delete in C/C++.

try to use again that texture. You'll probably see no texture.

And then try to load a new texture with same size, probably you will notice no memory usage increase.