Yes, private police organizations can be legal.
There is actually no such thing as "the police". What there actually is, is a series of organizations given "police powers" within certain areas of responsibility. This Wikipedia page shows just how many different types there actually are: Federal police (including some entire departments like the TSA), State police, county sheriffs & police, and the most well-known: municipal police.
Police powers are informally defined as Order maintenance, Law Enforcement, and Service. Any given police organization will be focused on a different balance of these, but the key aspect is that they have the power, granted by the government, to enforce laws. (ref) Any group which has police powers, public or private, is a police force.
This report which was prepared for the Department of Justice in 1971 refers to all the above government-run police forces as "Public Police". The report continues on to define private security forces (who do not have police powers), and "Special Police" which are
a small fraction of the privately employed security personnel ... [who] are granted either full or limited public police powers by virtue of being deputized or commissioned by local police or state agencies. The police powers of these special forces generally may be exercised only while on duty at a specified geographic location, such as their employer's or client's property. (emphasis mine)
This link has some of the more recent legal issues involved with private police, and notes that
Some states, including Georgia and South Carolina, have deputized security guards with much of the same authority as regular police officers. Other states, such as Arizona, have expressly provided that security guards do not have the same authority as regular police officers.
To bring this back around to your question it is probably not legal for an existing government-run organization to decide to incorporate as a private company, but it is definitely legal (in some jurisdictions) for a private company to be designated as police force. This means they are not run by the government, not directly funded by the government (i.e. the company is paid a contracted amount, then runs itself from that, rather than salaries and such coming directly from the government), and probably do not have the off-duty powers that public police officers have.
As my opinion, and I am not a lawyer or even a well-versed layman, the private organizations are legitimately keeping their records private, but the government should have a clause in their contract with them which can compel the organization to reveal these documents, if not one for regular record hand-over. If it doesn't, that's a failure of good governance.