Clustering with cosine similarity
First, every clustering algorithm is using some sort of distance metric. Which is actually important, because every metric has its own properties and is suitable for different kind of problems.

You said you have cosine similarity between your records, so this is actually a distance matrix. You can use this matrix as an input into some clustering algorithm.

Now, I'd suggest to start with hierarchical clustering - it does not require defined number of clusters and you can either input data and select a distance, or input a distance matrix (where you calculated the distance in some way).

Note that the hierarchical clustering is expensive to calculate, so if you have a lot of data, you can start with just sample.