I believe in older API versions (<38) there is no way to delete or modified any picklist value through the Metadata API.
The reason for it is because of data integrity. If the value you want to delete was used in at least one record, only from the configuration interface (point & click) you will be able to address that scenario.
When you are online (point & click), doing that type of operations, the message is something like:
"Use this page to globally replace an existing value in a picklist
with a new value. Choose a replacement value in the box below to apply
to any records that contain the deleted value. Choose "None" if you do
not want to change the value of existing records. The picklist no
longer contains the deleted value but records containing that value
still display it."
One workaround might be to remove the value at the level of the RecordType(s). Try to use the API to update your RecordType(s) and remove the value.
That was happening with older API versions (cannot say which version previous to 37). With API 38.0 we have the CustomValue and using it, we can Deactivate the values:
If picklist values are missing from a component definition, they get
deactivated when deployed. Deactivation occurs for picklist values of
both standard and custom fields.
For instance, for this picklist (you can get the file below if you fetch the CustomField and not the CustomObject):
<CustomObject xmlns="http://soap.sforce.com/2006/04/metadata">
<fields>
<fullName>Picklist1__c</fullName>
<externalId>false</externalId>
<label>Picklist1</label>
<required>false</required>
<type>Picklist</type>
<valueSet>
<valueSetDefinition>
<sorted>false</sorted>
<value>
<fullName>a</fullName>
<default>false</default>
</value>
<value>
<fullName>b</fullName>
<default>false</default>
</value>
<value>
<fullName>c</fullName>
<default>false</default>
</value>
</valueSetDefinition>
</valueSet>
</fields>
</CustomObject>
If we package and deploy the file without the value "c" it will be deactivated.
Before:

After:

What I cannot see is a way (API method) to delete the value and replace existing values with other active value or "blank".
Globally replace an existing value in a picklist with a new value.
Choose a replacement value below to apply to any records that contain
the deleted value. If you choose not to replace the value, the
picklist no longer contains the deleted value but records containing
that value still display it.
