This is one of those classes that you cannot override due to a bug in Magento.
Actually @Emipro was doing it correct but sadly the class UpdateHandler calls CreateHandler without the correct path thus instantiating it before the rewrite can ever be used. This is the current UpdateHandler:
namespace Magento\Catalog\Model\Product\Gallery;
use ...
class UpdateHandler extends CreateHandler
{...
In the "use" list the CreateHandler is not named and since it is in the same directory as de UpdateHandler the UpdateHandler instantiates this CreateHandler and uses it before Magento gets to your rewrite. What should have been there is:
namespace Magento\Catalog\Model\Product\Gallery;
use ...
class UpdateHandler extends Magento\Catalog\Model\Product\GalleryCreateHandler
{...
Sadly that is not the case. So what can you do? Simply rewrite both of them. Here is my rewrite and it works (but I still think Magento should fix this).
di.xml:
<preference for="Magento\Catalog\Model\Product\Gallery\CreateHandler" type="Vendor\ProductImporter\Model\Rewrite\Catalog\Model\Product\Gallery\CreateHandler" />
<preference for="Magento\Catalog\Model\Product\Gallery\UpdateHandler" type="Vendor\ProductImporter\Model\Rewrite\Catalog\Model\Product\Gallery\UpdateHandler" />
then because you have no choice but copy the whole file because of the "extend" part, in my directory Vendor\ProductImporter\Model\Rewrite\Catalog\Model\Product\Gallery I have the following:
namespace Vendor\ProductImporter\Model\Rewrite\Catalog\Model\Product\Gallery;
use ..[all the uses from the original file]
class UpdateHandler extends \Vendor\ProductImporter
\Model\Rewrite\Catalog\Model\Product\Gallery\CreateHandler
{
..[the rest of the original file]
So you can see the UpdateHandler now extends the correct way. And now I can use my rewrite of the CreateHandler and I want to make sure Magento does not make copies of my images with an underscore followed by an index (like image_1.png) so I want to rewrite the function moveImageFromTmp($file):
namespace Vendor\ProductImporter\Model\Rewrite\Catalog\Model\Product\Gallery;
class CreateHandler extends \Magento\Catalog\Model\Product\Gallery\CreateHandler
{
protected function moveImageFromTmp($file)
{ ... }
Note that I don't need the whole file here, I can extend it here as it should be extended. It is just the UpdateHandler that isn't correctly extending things...