Add the module back:
echo '[submodule "deps/haproxy-1.5"]
> path = deps/haproxy-1.5
> url = https://github.com/joyent/haproxy-1.5.git
> branch = joyent/v1.5.19
> ' >>.gitmodules
git add .gitmodules
git commit -m 1
Now officially remove it:
git submodule deinit -f deps/haproxy-1.5
git rm deps/haproxy-1.5
git commit -m 2