How not to lose quality of image with brush
When creating your texture that you are going to paint to, increase this number. (smaller is lower resolution, larger will allow for more detail) It is a good idea to keep powers of 2, such as 1024, 2048, 4096, 8192 Etc.



In your case, when you already have an image made, you can adjust the size of your image in the tools panel of the UV/Image Editor