hi,
thanks for reporting us.
It should be working in same way for Cleanup like for Avast Mobile Security (AMS) .
What happens on your second device - are you logged to same account in Google play as in case of AMS and you still get free version of Cleanup ?