I had the same problem and I found multiple issues. I am not an expert in this area, but here is a summary of the steps I took to resolve.  Hopefully it will be helpful:
Solving the HTTPS clone problem:
- Clone was failing with the error above, and I was not being prompted for my username and password on the command line.
Running clone with verbose flag - git clone --progress --verbose https://[my_gitlab_server]/[repo]/[project].git
 - showed git was pulling credentials from OSX Toolchain, which were apparently incorrect.  I disabled this using instructions here. - sudo git config --system --unset credential.helper
 
- I was now getting username and password prompt, but got: - remote: HTTP Basic: Access denied remote: You must use a personal access token with 'api' scope for Git over HTTP.
remote: You can generate one at https://[my_gitlab_server]/profile/personal_access_tokens
fatal: Authentication failed for 'https://[my_gitlab_server]/[repo]/[project].git/' - So I created a Personal Access Token as instructed here. 
- I was not sure what to do with the token.  Turns out you can include it in the URL as described here (for me that looked like - git clone https://oauth2:[token]@[my_gitlab_server]/[project].git) or you can just paste the token at the command line prompt for 'password'.
 
I could now clone via HTTPS.
Solving the SSH clone problem:
The SSH clone was giving the same error as the HTTPS clone. Some background on bash agents is helpful here.
- I found my ~/.ssh/config file in my user directory and verified the repo had an entry there. - Host [my_gitlab_server]/[repo]
IdentityFile ~/.ssh/id_rsa2
 
- I had multiple id-rsa files in the ssh directory, so I opened id_rsa2.pub (the one associated with my repo in the config file) and compared it to the key I found in my repo by navigating to the 'SSH Keys' tab in my 'Profile Settings'.  The keys were the same. - (If you need help creating and viewing keys see the docs here.) 
My keys were in place, but my SSH clone was still not working.  
- I thought there might be a problem with the config file or that my keys were no longer valid, so I bypassed the config file by manually adding the key to the current terminal session using instructions here. - eval $(ssh-agent -s)
ssh-add ~/.ssh/id_rsa2
 - This worked so I knew my key was valid. - (By the way, to see the keys loaded into your agent run - ssh-add -Land to see their fingerprints run- ssh-add -l.)
 
The problem now was that I needed to use the ~/.ssh/config file so I would not have to run eval and ssh-add every time I opened a new terminal window.
- To troubleshoot I ran ssh -Tvv git@[my_gitlab_server]which successfully connected to my gitlab server, but using a key I didn't recognize.  In the output I noticed that the file id-rsa2 was not searched.
- Using information from ssh.com about keys and ssh_config files, I found the  the /etc/private/ssh/ssh_config file specifies which keys are used.  The defaults were: - IdentityFile ~/.ssh/id_rsa
IdentityFile ~/.ssh/id_dsa
IdentityFile ~/.ssh/id_ecdsa
IdentityFile ~/.ssh/id_ed25519
 - I added my id_rsa2 key by running - sudo nano /private/etc/ssh/ssh_configand adding this line:
 - IdentityFile ~/.ssh/id_rsa2
 
This worked like a champ.
Overall its better to use a single ssh key with the default id_rsa name to avoid problems like this.