@cropredy answer is correct. But there are some changes in MetadataService class. So code given in above answer will not work. Below code will work with latest version of mdapi GitHub repo.
MetadataService.MetadataPort service = createService();
MetadataService.CustomField picklistField =(List<MetadataService.CustomField>) service.readMetadata('CustomField', 'Lead.picklist__c').getRecords();
metadataservice.CustomValue two = new metadataservice.CustomValue();
two.fullName= 'second';
two.default_x=false;
picklistField.valueSet.valueSetDefinition.value.add(two);
MetadataService.SaveResult result = service.updateMetadata( new MetadataService.Metadata[] { picklistField })[0];
In place of PicklistValue we have to use ValueSet.
Also we need to make little change in MetadataService Class. We have to replace ValueSet virtual class in Metadatservice with
public class ValueSet {
public String controllingField;
public Boolean restricted;
public MetadataService.ValueSetValuesDefinition valueSetDefinition;
public String valueSetName;
public MetadataService.ValueSettings[] valueSettings;
private String[] controllingField_type_info = new String[]{'controllingField',SOAP_M_URI,null,'0','1','false'};
private String[] restricted_type_info = new String[]{'restricted',SOAP_M_URI,null,'0','1','false'};
private String[] valueSetDefinition_type_info = new String[]{'valueSetDefinition',SOAP_M_URI,null,'0','1','false'};
private String[] valueSetName_type_info = new String[]{'valueSetName',SOAP_M_URI,null,'0','1','false'};
private String[] valueSettings_type_info = new String[]{'valueSettings',SOAP_M_URI,null,'0','-1','false'};
private String[] apex_schema_type_info = new String[]{SOAP_M_URI,'true','false'};
private String[] field_order_type_info = new String[]{'controllingField','restricted','valueSetDefinition','valueSetName','valueSettings'};
}
Also Check URL in your metadataPort.endpoint_x. It should be
public String endpoint_x = URL.getSalesforceBaseUrl().toExternalForm() + '/services/Soap/m/42.0';