The most likely cause of this behavior is the _beforeDelete method in app/code/core/Mage/Catalog/Model/Resource/Category.php, specifically this line:

$data = array('children_count' => new Zend_Db_Expr('children_count - ' . $childDecrease));

However, it is weird that you end up with a negative number here, since the children_count should increase when you first assign a category as a child. It could be that your custom code never increments the value in the first place, so definitely debug this, you may be doing something which is not "the Magento way". Since I do not know what your code looks like, I cannot say for sure, but definitely have a look at the core logic of the class I mentioned above.

You should fix the value manually after you have figured out what the problem was just to be on the safe side.

The most likely cause of this behavior is the _beforeDelete method in \Magento\Catalog\Model\ResourceModel\Category, specifically this line:

$this->getAggregateCount()->processDelete($object);

This will run processDelete() within \Magento\Catalog\Model\ResourceModel\Category\AggregateCount, which decreases children_count for all parent categories via:

$data = ['children_count' => new \Zend_Db_Expr('children_count - ' . $childDecrease)];
$where = ['entity_id IN(?)' => $parentIds];
$resourceModel->getConnection()->update($resourceModel->getEntityTable(), $data, $where);

However, it is weird that you end up with a negative number here, since the children_count should increase when you first assign a category as a child. It could be that your custom code never increments the value in the first place, so definitely debug this, you may be doing something which is not "the Magento way". Since I do not know what your code looks like, I cannot say for sure, but definitely have a look at the core logic of the class I mentioned above.

You should fix the value manually after you have figured out what the problem was just to be on the safe side.