Are you using the "Save Painting" or "Save Painting As..." options under the "File menu"? If so, that could be the problem. If it is, try using the "Export As Image..." option to save the image as .jpeg file instead.
If that isn't the problem, you should be able to scale the painting down using the "Rescale the Painting..." option (not to be confused with the "Resize Canvas" option) found in the "Edit" menu. If the image is resizing (in dimension) but you still get the message when you upload to the gallery or post, then it could be that the file size itself is to large (and not the dimensions). PNG files, for example, will be considerably larger in file size then a jpeg file of the same dimension.
Nothing is easy to the unwilling.