In photoshop, save as a .jpeg. Click: file>save as>(type file name)>save. In the quality box, move the slider to 0-3 for low quality. You probably won't get any pic smaller than 10k, though, unless the picture is like less than 200x200 pixels.
If you tried this already, what file type are you saving as... .jpeg, .gif, .bmp, etc?