I know I can get the public key from cleos for a given account but is the reverse possible? Basically, I am trying to find all the account names associated with a public key.
Yes, it's possible, you can just retrieve all the accounts for a given public key running the command
cleos get accounts EOS_PUB_KEY
Another way to check the accounts for a public key, from an external application, is using the EOS RPC Api, check this out: https://developers.eos.io/eosio-nodeos/reference#get_key_accounts-1